On Chvátal’s Conjecture for the Hamiltonicity of 1-Tough Graphs and Their Complements
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.
Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1340542Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 406
 D. Bauer, H. Broersma, E. Schmeichel, “Toughness in Graphs—A Survey”, Graphs and Combinatorics, vol. 22, 2006, pp. 1–35.
 V. Chvatal, “Tough Graphs and Hamiltonian Circuits”, Discrete Mathematics, vol. 306, 2006, pp. 910–917.
 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.
 L.-H. Hsu and C.-K. Lin, “Graph Theory and Interconnection Networks”, CRC Press, Taylor & Francis Group, New York, 2008.
 H. A. Jung, “On Maximal Circuits in Finite Graphs”, Annals of Discrete Mathematics, vol. 3, 1978, pp. 129–144.
 H. Li, “Generalization of Dirac’s Theorem in Hamiltonian Graph Theory - A Survey”, Discrete Mathematics, vol. 313, 2013, pp. 2034–2053.
 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.
 D. Bauer and E. F. Schmeichel, “Toughness and the Cycle Structure of Graphs”, Annals of Discrete Mathematics, vol. 55, 1993, pp. 145–152.