Abstract | ||
---|---|---|
For a graph G, we denote by δ(G) the minimum degree of G. A graph G is said to be claw-free if G has no induced subgraph isomorphic to K 1, 3. In this article, we prove that every claw-free graph G with minimum degree at least 4 has a 2-factor in which each cycle contains at least \({\big\lceil\frac{\delta(G) - 1}{2}\big\rceil}\) vertices and every 2-connected claw-free graph G with minimum degree at least 3 has a 2-factor in which each cycle contains at least δ(G) vertices. For the case where G is 2-connected, the lower bound on the length of a cycle is best possible. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1007/s00373-013-1375-z | Graphs and Combinatorics |
Keywords | Field | DocType |
claw free graph | Topology,Wheel graph,Discrete mathematics,Graph toughness,Combinatorics,Bound graph,Graph power,Cycle graph,Regular graph,Degree (graph theory),Factor-critical graph,Mathematics | Journal |
Volume | Issue | ISSN |
31 | 1 | 1435-5914 |
Citations | PageRank | References |
1 | 0.35 | 13 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Roman Cada | 1 | 40 | 8.35 |
Shuya Chiba | 2 | 35 | 12.93 |
Kiyoshi Yoshimoto | 3 | 133 | 22.65 |