Two Sufficient Conditions for Hamilton and Dominating Cycles

الملخص EN

We prove that if G is a 2-connect graph of size q (the number of edges) and minimum degree δ with δ≥2q/3+ϵ/12-1/2, where ϵ=11 when δ=2 and ϵ=31 when δ≥3, then each longest cycle in G is a dominating cycle.

The exact analog of this theorem for Hamilton cycles follows easily from two known results according to Dirac and Nash-Williams: each graph with δ≥q+5/4-1/2 is hamiltonian.

Both results are sharp in all respects.