##
**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 k^{2}+k+1 or if a = 1 and n \geq 2k^{2}-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