A sharp lower bound for the circumference of 1‐tough graphs with large degree sums
Vũ Đình Hòa · Journal of Graph Theory · 1995
Abstract We show that every 1‐tough graph G on n ≥ 3 vertices with σ3≧ n has a cycle of length at least min{n, n + (σ3/3 ) − α + 1}, where σ3 denotes the minimum value of the degree sum of any 3 pairwise nonadjacent vertices and α the cardinality of a miximum independent set of vertices in G. Our inequality is sharp and implies some sufficient conditions of hamiltonian cycles. © 1995 John Wiley & Sons, Inc.