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