Two sufficient conditions for Hamilton and dominating cycles (Q1935988)

Summary: We prove that if \(G\) is a 2-connected graph of size \(q\) (the number of edges) and minimum degree \(\delta\) with \(\delta \geq \sqrt{2q/3 + \epsilon/12} - 1/2\), where \(\epsilon = 11\) when \(\delta = 2\) and \(\epsilon = 31\) when \(\delta \geq 3\), then each longest cycle in \(G\) is a dominating cycle. The exact analog of this theorem for Hamiltonian cycles follows easily from two known results according to Dirac and Nash-Williams: each graph with \(\delta \geq \sqrt{q + 5/4} - 1/2\) is Hamiltonian. Both results are sharp in all respects.