Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6424546 | Journal of Combinatorial Theory, Series B | 2015 | 24 Pages |
Abstract
A graph G is said to be claw-free if G has no induced subgraph isomorphic to K1,3. For a cycle C in a graph G, C is called a Tutte cycle of G if C is a Hamilton cycle of G, or the order of C is at least 4 and every component of GâC has at most three neighbors on C. RyjáÄek (1997) [17] proved that the conjectures by Matthews and Sumner (every 4-connected claw-free graph is Hamiltonian) and by Thomassen (every 4-connected line graph is Hamiltonian) are equivalent. In this paper, we show the above conjectures are equivalent with the conjecture by Jackson in 1992 (every 2-connected claw-free graph has a Tutte cycle).
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Roman Äada, Shuya Chiba, Kenta Ozeki, Petr Vrána, Kiyoshi Yoshimoto,