A graph G is hypohamiltonian if G is not Hamiltonian, but G-v is Hamiltonian for each vV (V the vertex set of G). The smallest hypohamiltonian graph is the Petersen graphMathworldPlanetmathPlanetmath, which has ten vertices.

Title hypohamiltonian
Canonical name Hypohamiltonian
Date of creation 2013-03-22 12:25:24
Last modified on 2013-03-22 12:25:24
Owner digitalis (76)
Last modified by digitalis (76)
Numerical id 4
Author digitalis (76)
Entry type Definition
Classification msc 05C45
Classification msc 05C65
Related topic HamiltonianGraph
Related topic PetersensGraph