On Chvátal’s Conjecture for the Hamiltonicity of 1-Tough Graphs and Their Complements

Authors: Shin-Shin Kao, Yuan-Kang Shih, Hsun Su

Abstract:

In this paper, we show that the conjecture of Chv tal, which states that any 1-tough graph is either a Hamiltonian graph or its complement contains a specific graph denoted by F, does not hold in general. More precisely, it is true only for graphs with six or seven vertices, and is false for graphs with eight or more vertices. A theorem is derived as a correction for the conjecture.

Keywords: Complement, degree sum, Hamiltonian, tough.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1340542

References:

[1] D. Bauer, H. Broersma, E. Schmeichel, “Toughness in Graphs—A Survey”, Graphs and Combinatorics, vol. 22, 2006, pp. 1–35.
[2] V. Chvatal, “Tough Graphs and Hamiltonian Circuits”, Discrete Mathematics, vol. 306, 2006, pp. 910–917.
[3] D. Bauer, H. J. Broersma and H. J. Veldman, “Not every 2-tough graph is Hamiltonian”, Discrete Applied Mathematics, vol. 99, 2000, pp. 317–321.
[4] L.-H. Hsu and C.-K. Lin, “Graph Theory and Interconnection Networks”, CRC Press, Taylor & Francis Group, New York, 2008.
[5] H. A. Jung, “On Maximal Circuits in Finite Graphs”, Annals of Discrete Mathematics, vol. 3, 1978, pp. 129–144.
[6] H. Li, “Generalization of Dirac’s Theorem in Hamiltonian Graph Theory - A Survey”, Discrete Mathematics, vol. 313, 2013, pp. 2034–2053.
[7] D. Bauer and E. F. Schmeichel, “Long Cycles in Tough Graphs”, Steven’s Research Reports in Mathematics 8612, Steven’s Institute of Technology, Hoboken, New Jersey 07030, 1986.
[8] D. Bauer and E. F. Schmeichel, “Toughness and the Cycle Structure of Graphs”, Annals of Discrete Mathematics, vol. 55, 1993, pp. 145–152.