An Ore graph is a simple graph in which every pair of distinct nonadjacent vertices and satisfies
where is the vertex
set,
is the vertex count, and is the vertex degree of
(Ore 1960, Bondy 1971). The strict inequality
used by Skiena (1990, p. 197) and Pemmaraju and Skiena (2003, p. 301) is
a more restrictive hypothesis.
Under the conventions used here, is Hamiltonian, while
satisfies Ore's criterion but is not
Hamiltonian. Conversely, not every Hamiltonian
graph satisfies Ore's criterion. The numbers of unlabeled simpleHamiltonian 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.
Bondy, J. A. "Pancyclic Graphs I." J. Combin. Th.11, 80-84, 1971.Bondy, J. A. and Chvátal,
V. "A Method in Graph Theory." Disc. Math.15, 111-136, 1976.Meyniel,
M. "Une condition suffisante d'existence d'un circuit hamiltonien dans un graphe
orienté." J. Combin. Th.14, 137-147, 1973.Ore,
Ø. "Note on Hamilton Circuits." Amer. Math. Monthly67,
55, 1960. https://doi.org/10.2307/2308928.Palmer,
E. M. "The Hidden Algorithm of Ore's Theorem on Hamiltonian Cycles."
Computers Math. Appl.34, 113-119, 1997.Pemmaraju, S.
and Skiena, S. Computational
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge,
England: Cambridge University Press, 2003.Skiena, S. Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, 1990.Sloane, N. J. A. Sequences A264683
and A264684 in "The On-Line Encyclopedia
of Integer Sequences."Woodall, D. R. "Sufficient Conditions
for Circuits in Graphs." Proc. London Math. Soc.24, 739-755,
1972.
in which every pair of distinct nonadjacent vertices 
and 
satisfies
is the vertex
set, 
is the vertex count, and 
is the vertex degree of
(Ore 1960, Bondy 1971). The strict inequality
used by Skiena (1990, p. 197) and Pemmaraju and Skiena (2003, p. 301) is
a more restrictive hypothesis.
, 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.
is Hamiltonian, while
satisfies Ore's criterion but is not
Hamiltonian. Conversely, not every Hamiltonian
graph satisfies Ore's criterion. The numbers of unlabeled 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.
