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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page