×

A note on Hamiltonian circuits. (English) Zbl 0233.05123

The purpose of this note is to prove the following Theorem 1. Let \(G\) be a graph with at least three vertices. If, for some \(s\), \(G\) is \(s\)-connected and contains no independent set of more than \(s\) vertices, then \(G\) has a Hamiltonian circuit. This theorem is sharp. For \(s\) relatively large with respect to the number of vertices of \(G\), our Theorem 1 follows from a stronger statement due to Nash-Williams and Bondy [C. St. J. A. Nash-Williams, Studies pure Math., Papers presented to Richard Rado on the Occasion of his sixty-fifth Birthday, 157-183 (1971; Zbl 0223.05123), Lemma 4]. As an easy consequence of Theorem 1 we obtain Theorem 2. Let \(G\) be an \(s\)-connected graph with no independent set of \(s+2\) vertices. Then \(G\) has a Hamiltonian path. The technique used in the proof of Theorem 1 yields also Theorem 3. Let \(G\) be an \(s\)-connected graph containing no independnet set of \(s\) vertices. Then \(G\) is Hamiltonian-connected (i.e. every pair of vertices is joined by a Hamiltonian path).

MSC:

05C45 Eulerian and Hamiltonian graphs
05C38 Paths and cycles
05C40 Connectivity

Citations:

Zbl 0223.05123
Full Text: DOI

References:

[1] Dirac, G. A., Généralisation du théorème de Menger, C.R. Acad. Sci. Paris, 250, 26, 4252-4253 (1960) · Zbl 0095.37803
[2] Nash-Williams, J. A., Edge-disjoint Hamiltonian circuits in graphs with vertices of large valency, (Mirsky, L., Studies in pure mathematics (1971), Academic Press: Academic Press New York), (papers presented to Richard Rado) · Zbl 0223.05123
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.