Hamiltonian cycles in regular graphs of moderate degree

DOI10.1016/0095-8956(77)90063-6MaRDI QIDQ1245232zbMATH OpenOpenAlexFDO

Authors Arthur M. Hobbs, P. Erdős

Publication date 1977

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0095-8956(77)90063-6

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Review text

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)] .

Recommendations

• Hamilton cycles in regular 3-connected graphs
• scientific article; zbMATH DE number 3966120
• scientific article; zbMATH DE number 3929043
• Hamiltonicity in connected regular graphs
• Hamilton cycles in almost-regular 2-connected graphs

Cites work

• A class of Hamiltonian regular graphs
• scientific article; zbMATH DE number 3377257 (Why is no real title available?)
• Some Theorems on Abstract Graphs

Cited in

(22)

• Hamiltonian cycles in regular graphs
• Long path connectivity of regular graphs
• Dominating cycles in regular 3-connected graphs
• Hamilton cycles in regular 3-connected graphs
• Hamilton cycles in regular 2-connected graphs
• A remark on two sufficient conditions for Hamilton cycles
• Complexity of the hamiltonian cycle in regular graph problem
• A lower bound on the number of hamiltonian cycles
• Hamiltonicity, minimum degree and leaf number
• On Hamiltonicity of regular graphs with bounded second neighborhoods
• Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices
• Solution to a problem of Bollobás and Häggkvist on Hamilton cycles in regular graphs
• scientific article; zbMATH DE number 3896976 (Why is no real title available?)
• scientific article; zbMATH DE number 3929043 (Why is no real title available?)
• scientific article; zbMATH DE number 3966120 (Why is no real title available?)
• scientific article; zbMATH DE number 4127257 (Why is no real title available?)
• On the minimum number of Hamiltonian cycles in regular graphs
• scientific article; zbMATH DE number 3999970 (Why is no real title available?)
• scientific article; zbMATH DE number 908781 (Why is no real title available?)
• Loose Hamilton Cycles in Regular Hypergraphs
• On regular 2-path Hamiltonian graphs
• Hamilton cycles in almost-regular 2-connected graphs

This page was built for publication: Hamiltonian cycles in regular graphs of moderate degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1245232)