Article ID Journal Published Year Pages File Type
6424546 Journal of Combinatorial Theory, Series B 2015 24 Pages PDF
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
, , , , ,