Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 32718
On Chvátal’s Conjecture for the Hamiltonicity of 1-Tough Graphs and Their Complements

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


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):

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 625


[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.