2012/08/27 by Zh. G. Nikoghosyan, Nikoghosyan, Zh. G.
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems #math.CO
paper · pdf · doi:10.48550/arxiv.1208.5463
11 pages, corrected and improved version
openalex publication_date 2012/08/27 · arxiv created 2012/09/17 · arxiv updated 2012/09/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In 1973, Chvátal introduced the concept of toughness τ of a graph and constructed an infinite class of nonhamiltonian graphs with τ=3/2. Later Thomassen found nonhamiltonian graphs with τ>3/2, and Enomoto et al. constructed nonhamiltonian graphs with τ=2-ε for each positive ε. The last result in this direction is due to Bauer, Broersma and Veldman, which states that for each positive ε, there exists a nonhamiltonian graph with τ≥ 9/4-ε. In this paper we prove that for each rational number t with 0<t<9/4, there exists a nonhamiltonian graph with τ=t.