Non-hamiltonian Graphs with Given Toughness


  • Zhora G. Nikoghosyan Institute for Informatics and Automation Problems of NAS RA


Hamilton cycle, Toughness of graph


In 1973, Chvátal introduced the concept of toughness τ of a graph and conjectured that there exists a finite constant t0 such that every t0-tough graph (that is τ ≥ t0) is hamiltonian. To solve this challenging problem, all efforts are directed towards constructing non-hamiltonian graphs with toughness as large as possible. The last result in this direction is due to Bauer, Broersma and Veldman, which states that for each positive ϵ, there exists a non-hamiltonian graph with 9/4 - ϵ ≤ τ < 9/4. The following related broad-scale problem, reminding the well-known pancyclicity or hypohamiltonicity, arises naturally: whedher there exists a non-hamiltonian graph with a given toughness. We conjecture that if there exist a non-hamiltonian t-tough graph then for each rational number a with 0 < a ≤ t there exists a non-hamiltonian graph whose toughness is exactly a. In this paper we prove this conjecture for t = 9/4 - ϵ by using a number of additional modified building blocks to construct the required graphs.


D. Bauer, H. J. Broersma, J. van den Heuvel and H. J. Veldman, “On Hamiltonian properties of 2-tough graphs", J. Graph Theory, vol. 18, pp. 539-543, 1994.

D. Bauer, H. J. Broersma and H. J. Veldman, “Not every 2-tough graph is hamiltonian", Discrete Appl. Math., vol. 99, pp. 317-321, 2000.

D. Bauer and E. Schmeichel, “Toughness, minimum degree and the existence of 2-factors", J. Graph Theory, vol. 18, pp. 241-256, 1994.

J. C. Bermond, Selected Topics in Graph Theory, in: L. Beineke, R. J. Wilson (eds), Academic Press, London and New York, 1978.

J. A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan, London and Elsevier, New York, 1976.

V. Chvátal, “Tough graphs and Hamiltonian circuits", Discrete Math., vol. 5, pp. 215-228, 1973.

H. Enomoto, B. Jackson, P. Katerinis and A. Saito, “Toughness and the existence of k-factors", J. Graph Theory, vol. 9, pp. 87-95, 1985.




How to Cite

Nikoghosyan, Z. G. (2021). Non-hamiltonian Graphs with Given Toughness. Mathematical Problems of Computer Science, 40, 13–22. Retrieved from