Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  374.05037
Autor:  Erdös, Paul; Hobbs, Arthur M.
Title:  Hamiltonian cycles in regular graphs of moderate degree. (In English)
Source:  J. Comb. Theory, Ser. B 23, 139-142 (1977).
Review:  It is shown that if k is an integer no less than 3, and if G is a 2-connected graph with 2n-a vertices, a in {0,1}, which is regular of degree n-k, then G is Hamiltonian if a = 0 and n \geq k2+k+1 or if a = 1 and n \geq 2k2-3k+3. Subsequently, B.Bollobás and A.M.Hobbs have proved a stronger result in [Ann. Discrete Math. 3, 43-49 (1978; Zbl 376.05036)] , and more recently, W.Jackson has obtained the best possible result that a 2-connected k-regular graph with at most 3k vertices is Hamiltonian [J. Comb. Theory, Ser. B 29, 27-46 (1980; Zbl 432.05037)] .
Reviewer:  C.Thomassen
Classif.:  * 05C35 Extremal problems (graph theory)

© 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