A Sharp Improvement of a Theorem of Bauer and Schmeichel


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




Hamilton cycle, circumference, minimum degree, 1-tough graphs


Let G be a graph on n vertices with minimum degree δ. The earliest nontrivial lower bound for the circumference c (the length of a longest cycle in G) was established in 1952 due to Dirac in terms of n and δ: (i) if G is a 2-connected graph, then c ≥ min{n, 2δ}. The bound in Theorem (i) is sharp. In 1986, Bauer and Schmeichel gave a version of this classical result for 1-tough graphs: (ii) if G is a 1-tough graph, then c ≥ min{n, 2δ + 2}. In this paper we present an improvement of (ii), which is sharp for each n: (iii) if G is a 1-tough graph, then c ≥ min{n, 2δ + 2} when n ≡ 1(mod 3); c ≥ min{n, 2δ + 3} when n ≡ 2(mod 3) or n ≡ 1(mod 4); and c ≥ min{n, 2δ + 4} otherwise.


D. Bauer and E. Schmeichel, Long cycles in tough graphs, Technical Report 8612, Stevens Institute of Technology, 1986.

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.

G. A. Dirac, “Some theorems on abstract graphs", Proc. London, Math. Soc., vol. 2, pp. 69-81, 1952.

H.-J. Voss, “Bridges of longest circuits and of longest paths in graphs", Beitrage zur Graphentheorie und deren Anwendungen, Vorgetr. auf dem. int. Kolloq., Oberhof (DDR), pp. 275-286, 1977.




How to Cite

Nikoghosyan, Z. G. (2021). A Sharp Improvement of a Theorem of Bauer and Schmeichel. Mathematical Problems of Computer Science, 50, 15–34. https://doi.org/10.51408/1963-0017