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

给定连通图集合Φ,对图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}-因子.现给出这个猜想的证明.

Path and cycle factors of cubic graphs

For a set of connected graphs, a spanning subgraph of a graph is called an -factor if every component of is isomorphic to a member of . It was recently shown by Kawarabayashi et al. that every 2-connected cubic graph has a -factor and -factor, where denote the cycle of order n and denote the path of order n. Kano et al. show that every connected cubic bipartite graph has a -factor and -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 -factor. In this paper, we give a proof of this conjecture.