Category:Definitions/Complements of Graphs
Jump to navigation
Jump to search
This category contains definitions related to Complements of Graphs.
Related results can be found in Category:Complements of Graphs.
Simple Graph
Let $G = \struct {V, E}$ be a simple graph.
The complement of $G$ is the simple graph $\overline G = \struct {V, \overline E}$ which consists of:
- The same vertex set $V$ of $G$
- The set $\overline E$ defined such that $\set {u, v} \in \overline E \iff \set {u, v} \notin E$, where $u$ and $v$ are distinct.
Loop-Graph
Let $G = \struct {V, E}$ be a loop-graph.
The complement of $G$ is the loop-graph $\overline G = \struct {V, \overline E}$ which consists of:
- The same vertex set $V$ of $G$;
- The set $\overline E$ defined such that:
- $\set {u, v} \in \overline E \iff \set {u, v} \notin E$
- $\set {v, v} \in \overline E \iff \set {v, v} \notin E$
That is, the complement $\overline G$ of a loop-graph $G$ has loops on all vertices where there are no loops in $G$.
Pages in category "Definitions/Complements of Graphs"
The following 5 pages are in this category, out of 5 total.