Hamiltonian cycles in regular graphs of moderate degree (Q1245232)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Hamiltonian cycles in regular graphs of moderate degree
scientific article

    Statements

    Hamiltonian cycles in regular graphs of moderate degree (English)
    0 references
    0 references
    0 references
    1977
    0 references
    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, \textit{B.Bollobás} and \textit{A.M.Hobbs} have proved a stronger result in [Ann. Discrete Math. 3, 43-49 (1978; Zbl 0376.05036)] , and more recently, \textit{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 0432.05037)] .
    0 references

    Identifiers