Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 233.05123
Autor: Chvatal, V.; Erdös, Paul
Title: A note on Hamiltonian circuits. (In English)
Source: Discrete Math. 2, 111-113 (1972).
Review: 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 223.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).
Classif.: * 05C45 Eulerian and Hamiltonian graphs
05C38 Paths and cycles
05C40 Connectivity
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag