[Math] When is graph G with n vertices is isomorphic to complement $\bar G$

graph theory

Question : When is graph G with n vertices is isomorphic to complement $\bar G$?

So, total no of edges that a n vertex graph can have is = $n \choose 2$. And if G is isomorphic to $\bar G$ then no of edges in G is equal to no of edges in $\bar G$. So no of edges in G = $\frac{1}{2}$$ n \choose 2$ . But for this to be an integer, n = 4k or n = 4k+1 for some integer k.

My question is : Is this the only requirement? That is, is $n = 4k$ or $4k+1$ the sufficient condition to construct such a graph G? Does it have anything to do with the fact that G and $\bar G$ can both be bipartite if both of them don't have any triangle in it? The question asks to think about what is the condition of G and $\bar G$ simultaneously bipartite.

Best Answer

Let $n=4k$. Then the following graph $G$ is self-complementary: Let $V=\{1,2,\ldots, 4k\}$, add edges between $u$ and $v$ if

  • both $u,v$ are $\le 2k$ or
  • exactly one of $u,v$ is $\le k$ and $|u-v|$ is even.

Then $$\tag1x\mapsto\begin{cases}x+2k&\text{if }x\le 2k\\x-2k+1&\text{if }2k<x<4k\\1&\text{if }x=4k\end{cases}$$ is an isomorphism of $G$ with its complement $\bar G$.

Now let $n=4k+1$. Start with the graph $G$ constructed for $n=4k$ and add a new vertex $0$. Add edges from $0$ to $x$ for $1\le x\le 2k$. The map $(2)$ extended by mapping $0\mapsto 0$ is an isomorphism of this new graph $G'$ with its complement $\overline {G'}$.

Related Question