A 2-factor in which each cycle has long length in claw-free graphs
A 2-factor in which each cycle has long length in claw-free graphs
复制标题
无爪图中每个周期具有较长长度的 2 因子
DOI：
10.1007/s00373-013-1375-z
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
S. Chiba and K. Yoshimoto
中科院分区：
文献类型：
--
作者：
R. Cada;S. Chiba and K. Yoshimoto
对于图G，我们用δ（G）表示G的最小度。一个图G称为无爪图，如果G没有同构于K1，3的导出子图。本文证明了最小度至少为4的无爪图G有一个2-因子，其中每个圈至少包含个顶点;最小度至少为3的2-连通无爪图G有一个2-因子，其中每个圈至少包含δ（G）个顶点。对于G是2-连通的情况，圈长的下界是最佳可能的。
For a graphG, we denote byδ(G) the minimum degree ofG. A graphGis said to be claw-free ifGhas no induced subgraph isomorphic toK1, 3. In this article, we prove that every claw-free graphGwith minimum degree at least 4 has a 2-factor in which each cycle contains at leastvertices and every 2-connected claw-free graphGwith minimum degree at least 3 has a 2-factor in which each cycle contains at leastδ(G) vertices. For the case whereGis 2-connected, the lower bound on the length of a cycle is best possible.