Nonhamiltonian Graphs with Given Toughness

MaRDI QIDQ6235261zbMATH OpenFDO

Authors Zh. G. Nikoghosyan

Publication date 27 August 2012

Abstract: In 1973, Chv'{a}tal introduced the concept of toughness $au$ of a graph and constructed an infinite class of nonhamiltonian graphs with $au=3/2$. Later Thomassen found nonhamiltonian graphs with $au>3/2$, and Enomoto et al. constructed nonhamiltonian graphs with $au=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 $auge9/4-epsilon$. In this paper we prove that for each rational number $t$ with $0<t<9/4$, there exists a nonhamiltonian graph with $au=t$.

This page was built for publication: Nonhamiltonian Graphs with Given Toughness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6235261)