Neil Sharp

Answered

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 $(}\genfrac{}{}{0ex}{}{n}{2}{\textstyle )$. 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 $(}\genfrac{}{}{0ex}{}{n}{2}{\textstyle )$ . 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.

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 $(}\genfrac{}{}{0ex}{}{n}{2}{\textstyle )$. 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 $(}\genfrac{}{}{0ex}{}{n}{2}{\textstyle )$ . 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.

Answer & Explanation

Jayda King

Expert

2022-11-26Added 8 answers

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

$\begin{array}{}\text{(1)}& x\mapsto \{\begin{array}{ll}x+2k& \text{if}x\le 2k\\ x-2k+1& \text{if}2kx4k\\ 1& \text{if}x=4k\end{array}\end{array}$

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

both $u,v$ are $\le 2k$ or

exactly one of $u,v$ is $\le k$ and $|u-v|$ is even.

Then

$\begin{array}{}\text{(1)}& x\mapsto \{\begin{array}{ll}x+2k& \text{if}x\le 2k\\ x-2k+1& \text{if}2kx4k\\ 1& \text{if}x=4k\end{array}\end{array}$

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

Most Popular Questions