Hamiltonian Graph

• A Hamiltonian Path is a path contained within a graph such that it passes through vertex exactly once.

• A Hamiltonian Cycle is a cycle contained within a Graph such that it passes through each vertex exactly once.

• A Hamiltonian Graph is a graph which contains a Hamiltonian Cycle

• A graph is Semi-Hamiltonian if it contains a Hamiltonian Path but not a Hamiltonian Cycle

• (Bondy and Murty 4.2) If is Hamiltonian, then for every non-empty .

• (Bondy and Murty 4.3) Dirac’s Theorem. If is a graph with vertices and then is Hamiltonian.

• (Wilson 7.1) Ore’s Theorem ¹. Let be a simple graph with vertices. If for each pair of non-adjacent vertices and , then is Hamiltonian

• (Godsil 3.6.1) Let be a cubic graph, then has a Hamiltonian cycle if and only if does.

Links §

• Introduction To Graph Theory by Wilson
• Graph Theory With Applications by Bondy and Murty
• Godsil and Royle

Footnotes §

1. Ore’s Theorem generalizes Dirac’s Theorem ↩