TOPICS
Search

Ore Graph


An Ore graph is a graph that satisfies Ore's theorem, i.e., a graph G for which the sums of the degrees of nonadjacent vertices is greater than or equal to the number of nodes n for all subsets of nonadjacent vertices. Let V(G) be the vertex set and E(G) the edge set of G, let |V(G)| denote the vertex count of G, let denote the vertex degree of vertex v by d(v), and let (u,v) denote a pair of vertices. The condition for G to be an Ore graph can then be written

 (u,v) not in E(G)=>d(u)+d(v)>=|V(G)|

(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."

OreGraphs

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 n=1, 2, ... satisfying Ore's criterion (using the "vacuous truth" convention and so including complete graphs K_n) are 1, 1, 1, 3, 5, 21, 68, 503, 4942, 128361, ... (OEIS A264683), the first few of which are illustrated above.

HamiltonianNonOreGraph

Every graph satisfying Ore's criterion is Hamiltonian, but not every Hamiltonian graph satisfies the criterion. The numbers of simple Hamiltonian graphs on n=1, 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.


See also

Hamiltonian Cycle, Hamiltonian Graph, Ore's Theorem

Explore with Wolfram|Alpha

References

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, O. "A Note on Hamiltonian Circuits." Amer. Math. Monthly 67, 55, 1960.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.

Referenced on Wolfram|Alpha

Ore Graph

Cite this as:

Weisstein, Eric W. "Ore Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/OreGraph.html

Subject classifications