Hamiltonian graph
A graph is Hamiltonian if it has a Hamiltonian cycle.
A useful condition both necessary and sufficient for a graph to be Hamiltonian is not known. Ore’s theorem and the Bondy and Chvátal theorem give sufficient conditions, while a necessary condition follows quickly from the definition, namely:
Let be a graph of order at least 3. If is Hamiltonian, then for every proper subset of , the subgraph induced by has at most components.
Title | Hamiltonian graph |
Canonical name | HamiltonianGraph |
Date of creation | 2013-03-22 11:52:43 |
Last modified on | 2013-03-22 11:52:43 |
Owner | drini (3) |
Last modified by | drini (3) |
Numerical id | 13 |
Author | drini (3) |
Entry type | Definition |
Classification | msc 05C45 |
Classification | msc 55-00 |
Classification | msc 82-00 |
Classification | msc 83-00 |
Classification | msc 81-00 |
Synonym | Hamiltonian |
Related topic | HamiltonianCycle |
Related topic | HamiltonianPath |
Related topic | OresTheorem |
Related topic | BondyAndChvatalTheorem |
Related topic | PetersensGraph |
Related topic | Traceable |