Definition:Ore Graph
Jump to navigation
Jump to search
Definition
Let $G = \struct {V, E}$ be an undirected simple graph.
Then $G$ is an Ore graph if and only if:
- the sum of the degrees of every pair of non-adjacent vertices is greater than or equal to the order of $G$.
That is, if and only if:
- $\forall u, v \in V: \set {u, v} \notin E \implies \map {\deg_G} u + \map {\deg_G} v \ge \card V$
Also see
- Results about Ore graphs can be found here.
Source of Name
This entry was named for Øystein Ore.
Sources
- Weisstein, Eric W. "Ore Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/OreGraph.html