Premium
Hamiltonian cycles in 2‐connected claw‐free‐graphs
Author(s) -
Li Hao
Publication year - 1995
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190200408
Subject(s) - combinatorics , mathematics , disjoint sets , claw , vertex (graph theory) , graph , hamiltonian path , bound graph , upper and lower bounds , hamiltonian (control theory) , discrete mathematics , graph power , line graph , mathematical analysis , mechanical engineering , mathematical optimization , engineering
M. Matthews and D. Sumner have proved that of G is a 2‐connected claw‐free graph of order n such that δ ≧ ( n − 2)/3, then G is hamiltonian. We prove that the bound for the minimum degree δ can be reduced to n /4 under the additional condition that G is not in F , where F is the set of all graphs defined as follows: any graph H in F can be decomposed into three vertex disjoint subgraphs H 1 , H 2 , H 3 such that, where u i , v i ϵ V ( H i ), u j v j ϵ V ( H j ) 1 ϵ i ≦ j ≦ 3. Examples are given to show that the bound n /4 is sharp. © 1995 John Wiley & Sons, Inc.