字典序地生成叶子数限制的有序根树的算法

本文利用一个正整数序列来表示一棵叶子数限制的有序根树,给出了一个序列为某叶子数限制的有序根树的表示序列的充要条件,从而给出了字典序地生成所有叶子数限制的有序根树的算法.§1.叶子数限制的有序根树的序列表示法设T表示有序根树,用|T|表示T的边树.若v是T的顶点,v不是根且次数为1,则称v是T的叶子.     

(4, k)-Factor-Critical Graphs and Toughness

WorksupportedbytheNSFCandtheNationalEducationCommissionDoctoralFoundationofChian.WorksupportedbyNaturalSciencesandEngineeringResearchCouncilofCanadaundergrantOGP0122059andUniversityCollegeoftheCaribooScholarlyActivityCrant.Thegraphsconsideredinthispaperaresimpleandfinite.LetGbegraphwithvertexsetV(G)andedgesetE(G).Ak-factorofGisaspanningsubgrapliFofGsuchthatdF(x)=kforeachx6V(G),wheredF(x)denotesthedegreeofxinF.ThetoughnessofG,t(G),isdefinedasthefollowing:wherew(G--S)isthenumbe…     

关于图的星形因子覆盖

如果图 G 的支撑子图 M 的每个分支都同构于{K_(1,1)K_(1,2,)…,K_(1,k}(k≥2)中的某个 K_(1,i),则 M(?)叫做 G 的星形因子。进一步,如果对于图 G 的每一条边都存在一个星形因子包含这条边,则称图 G 是星形因子覆盖的。本文给出了图是{P_2,P_3}一因子覆盖的充要条件,并证明了任意正则图均存在星形因子覆盖。