✦ LIBER ✦
A sharp lower bound for the circumference of 1-tough graphs with large degree sums
✍ Scribed by Vu Dinh Hoa
- Publisher
- John Wiley and Sons
- Year
- 1995
- Tongue
- English
- Weight
- 207 KB
- Volume
- 20
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
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.