# A Sharp Improvement of a Theorem of Bauer and Schmeichel

## DOI:

https://doi.org/10.51408/1963-0017## Keywords:

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

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.

## References

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.

## Downloads

## Published

## How to Cite

*Mathematical Problems of Computer Science*,

*50*, 15–34. https://doi.org/10.51408/1963-0017

## Issue

## Section

## License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.