Ore Graph
An Ore graph is a graph that satisfies Ore's theorem, i.e., a graph 
for which the sums of the degrees of
nonadjacent vertices is greater than or equal to the number of nodes 
for all subsets
of nonadjacent vertices. Let 
be the vertex
set and 
the edge
set of 
, let 
denote the
vertex count of 
, let denote the
vertex degree of vertex 
by 
, and let 
denote a pair of vertices. The condition for 
to be an Ore graph
can then be written
 |
(Ore 1960; Bondy 1971). Note that Skiena (1990, p. 197) and Pemmaraju and Skiena (2003, p. 301) state a weaker version of this result with the "greater or equal than" replaced by "greater than."
Ore's theorem states that Ore graphs are always Hamiltonian. Furthermore, for such graphs, a Hamiltonian cycle can be constructed in polynomial
time (Bondy and Chvátal 1976; Skiena 1990, p. 197). The numbers of
graphs on 
, 2, ... satisfying Ore's criterion
(using the "vacuous truth" convention and so including complete
graphs 
) are 1, 1, 1, 3, 5, 21, 68, 503, 4942,
128361, ... (OEIS A264683), the first few of
which are illustrated above.
Every graph satisfying Ore's criterion is Hamiltonian, but not every Hamiltonian graph satisfies the
criterion. The numbers of simple Hamiltonian graphs on 
, 2, ... vertices
that do not satisfy Ore's criterion are 0, 0, 0, 0, 3, 27, 315, 5693, 172141, 9176757,
... (OEIS A264684), the first few of which
are illustrated above.
Contact the MathWorld Team
12th maxterm in 4 variables