Nonhamiltonian Graphs with Given Toughness

Abstract

In 1973, Chvátal introduced the concept of toughness $\tau$ of a graph and constructed an infinite class of nonhamiltonian graphs with $\tau =3/2$. Later Thomassen found nonhamiltonian graphs with $\tau >3/2$, and Enomoto et al. constructed nonhamiltonian graphs with $\tau =2-\epsilon$ for each positive $\epsilon$. The last result in this direction is due to Bauer, Broersma and Veldman, which states that for each positive $\epsilon$, there exists a nonhamiltonian graph with $\tau \ge 9/4-\epsilon$. In this paper we prove that for each rational number $t$ with $0<t<9/4$, there exists a nonhamiltonian graph with $\tau =t$.

arXiv comment11 pages, corrected and improved version