Neil Sharp

2022-11-25

When is graph G with n vertices is isomorphic to complement $\overline{G}$?
Question : When is graph G with n vertices is isomorphic to complement $\overline{G}$?
So, total no of edges that a n vertex graph can have is $\left(\genfrac{}{}{0}{}{n}{2}\right)$. And if G is isomorphic to $\overline{G}$ then no of edges in G is equal to no of edges in $\overline{G}$. So no of edges in $\left(\genfrac{}{}{0}{}{n}{2}\right)$ . 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 $\overline{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 $\overline{G}$ simultaneously bipartite.

Jayda King

Expert

Let n=4k. Then the following graph G is self-complementary: Let $V=\left\{1,2,\dots ,4k\right\}$, 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

is an isomorphism of G with its complement $\overline{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↦0$ is an isomorphism of this new graph ${G}^{\prime }$ with its complement $\overline{{G}^{\prime }}$.

Do you have a similar question?