Premium
Essential independent sets and Hamiltonian cycles
Author(s) -
Chen Guantao,
Egawa Yoshimi,
Liu Xin,
Saito Akira
Publication year - 1996
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/(sici)1097-0118(199602)21:2<242::aid-jgt15>3.0.co;2-l
Subject(s) - mathematics , combinatorics , hamiltonian path , hamiltonian (control theory) , graph , upper and lower bounds , independent set , discrete mathematics , mathematical analysis , mathematical optimization
An independent set S of a graph G is said to be essential if S has a pair of vertices distance two apart in G . We prove that if every essential independent set S of order k ≥ 2 in a k ‐connected graph of order p satisfies max {deg v : v ϵ S} ≥ ½ p , then g is hamiltonian. This generalizes the result of Fan ( J. Combinatorial Theory B 37 (1984), 221–227). If we consider the essential independent sets of order k + 1 instead of k in the assumption of the above statement, we can no longer assure the existence a hamiltonian cycle. However, we can still give a lower bound to the length of a longest cycle. © 1996 John Wiley & Sons, Inc.