Self Complementary Graphs

Self Complementary Graphs

Definition: A graph $G = (V(G), E(G))$ is said to be Self Complementary if $G$ is isomorphic to its complement, that is $G \cong \bar{G}$.

For example, the following graph $G$ and its complement are isomorphic as both can be "unravelled" into a path graph:

Screen%20Shot%202014-04-11%20at%2010.40.02%20AM.png

Note that for a graph to isomorphic to another in general, then the number of vertices in both graphs must be the same. Of course, this is no problem for complement graphs since they have the same vertex set. Additionally, for a graph to be isomorphic to another, the number of edges in both graphs must be the same. Hence if $\mid E(G) \mid \neq \mid E(\bar{G}) \mid$, then $G$ is not isomorphic. We also note that if:

(1)
\begin{align} \quad \mid E(G) \mid \neq \mid E(\bar{G}) \mid \neq \frac{n(n-1)}{4} \end{align}

Then the graph is NOT complementary. Notice that all we did was take the number of edges in the complete graph and divide it by $2$.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License