立方图中的路因子和圈因子  

Path and Cycle Factors of Cubic Graphs

作　　者：杜彩凤[1] 

机构地区：[1]中国石油大学(华东),东营257061

出　　处：《科学技术与工程》2010年第27期6709-6711,共3页Science Technology and Engineering

摘　　要：给定连通图集合Φ,对图G的生成子图F,如果F的每个分支都同构于集合Φ的一个元素,则F被称为G的Φ-因子。最近Kawarabayashi等证明了:2-连通立方图有一个{Cn|n≥4}-因子和{pn|n≥6}-因子,其中Cn表示阶为n的圈,Pn表示阶为n的路。Kano等给出了每一个阶至少为8的立方偶图有{Cn|n≥6}-因子和{pn|n≥8}-因子的结论,并且提出猜想:阶至少为6的3-连通立方图有{Cn|n≥5}-因子和{pn|n≥7}-因子。现给出这个猜想的证明。For a set Φ of connected graphs,a spanning subgraph F of a graph is called an Φ-factor if every component of F is isomorphic to a member of Φ.It was recently shown by Kawarabayashi et al.that every 2-connected cubic graph has a {Cn｜n≥4}-factor and {pn｜n≥6}-factor,where Cn denote the cycle of order n and Pn denote the path of order n.Kano et al.show that every connected cubic bipartite graph has a {Cn｜n≥6}-factor and {pn｜n≥8}-factor if its order is at least 8.And they have conjectured that every 3-connected cubic graph of order at least six has a{Cn｜n≥5}-factor.A proof of this conjecture is given.

关 键 词：路因子 圈因子 立方图 正则图 

分 类 号：O157.5[理学—数学]