Related Results
Ore's theorem is a generalization of Dirac's theorem that, when each vertex has degree at least n/2, the graph is Hamiltonian. For, if a graph meets Dirac's condition, then clearly each pair of vertices has degrees adding to at least n.
In turn Ore's theorem is generalized by the Bondy–Chvátal theorem. One may define a closure operation on a graph in which, whenever two nonadjacent vertices have degrees adding to at least n, one adds an edge connecting them; if a graph meets the conditions of Ore's theorem, its closure is a complete graph. The Bondy–Chvátal theorem states that a graph is Hamiltonian if and only if its closure is Hamiltonian; since the complete graph is Hamiltonian, Ore's theorem is an immediate consequence.
Woodall (1972) found a version of Ore's theorem that applies to directed graphs. Suppose a digraph G has the property that, for every two vertices u and v, either there is a vertex from u to v or the outdegree of u plus the indegree of v equals or exceeds the number of vertices in G. Then, according to Woodall's theorem, G contains a directed Hamiltonian cycle. Ore's theorem may be obtained from Woodall by replacing every edge in a given undirected graph by a pair of directed edges.
Ore's theorem may also be strengthened to give a stronger condition than Hamiltonicity as a consequence of the degree condition in the theorem. Specifically, every graph satisfying the conditions of Ore's theorem is either a regular complete bipartite graph or is pancyclic (Bondy 1971).
Read more about this topic: Ore's Theorem
Famous quotes containing the words related and/or results:
“Just as a new scientific discovery manifests something that was already latent in the order of nature, and at the same time is logically related to the total structure of the existing science, so the new poem manifests something that was already latent in the order of words.”
—Northrop Frye (b. 1912)
“Pain itself can be pleasurable accidentally in so far as it is accompanied by wonder, as in stage-plays; or in so far as it recalls a beloved object to one’s memory, and makes one feel one’s love for the thing, whose absence gives us pain. Consequently, since love is pleasant, both pain and whatever else results from love, in so far as they remind us of our love, are pleasant.”
—Thomas Aquinas (c. 1225–1274)