The Chvátal–Erdős Condition for a Graph to Have a Spanning Trail

Chvátal and Erdős proved a well-known result that every graph \(G\) with connectivity \(\kappa (G)\) not less than its independence number \(\alpha (G)\) is Hamiltonian. Han et al. (in Discret Math 310:2082–2090, 2003) showed that every 2-connected graph \(G\) with \(\alpha (G)\le \kappa (G)+1\) is supereulerian with some exceptional graphs. In this paper, we investigate the similar conditions and show that every 2-connected graph \(G\) with \(\alpha (G)\le \kappa (G)+3\) has a spanning trail. We also show that every connected graph \(G\) with \(\alpha (G)\le \kappa (G)+2\) has a spanning trail or \(G\) is the graph obtained from \(K_{1,3}\) by replacing at most two vertices of degree 1 in \(K_ {1,3}\) with a complete graph or \(G\) is the graph obtained from \(K_{3}\) by adding a pendent edge to each vertex of \(K_{3}\). As a byproduct, we obtain that the line graph of a connected graph \(G\) with \(\alpha (G)\le \kappa (G)+2\) is traceable. These results are all best possible.

The authors are greatly indebted to the referees for their careful comments. This work is supported by the Natural Science Funds of China (No: 11471037 and No: 11171129) and by Specialized Research Fund for the Doctoral Program of Higher Education (No. 20131101110048).

Authors and Affiliations

1. School of Mathematics, Beijing Institute of Technology, Beijing, 100081, People’s Republic of China

   Runli Tian & Liming Xiong

2. School of Science, Central South University of Forestry and Technology, Changsha, 410004, People’s Republic of China

   Runli Tian

Corresponding author

Correspondence to Liming Xiong.

Reprints and permissions