Definition:Ore Graph

From ProofWiki
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