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
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