Hamiltonian graph

A graph G is Hamiltonian if it has a Hamiltonian cycleMathworldPlanetmath.

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 G=(V,E) be a graph of order at least 3. If G is Hamiltonian, then for every proper subsetMathworldPlanetmathPlanetmath U of V, the subgraphMathworldPlanetmath induced by V-U has at most |U| 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