When is graph G with n vertices is isomorphic to complement G ¯ ?Question :...

Neil Sharp

Neil Sharp

Answered

2022-11-25

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

Answer & Explanation

Jayda King

Jayda King

Expert

2022-11-26Added 8 answers

Let n=4k. Then the following graph G is self-complementary: Let V = { 1 , 2 , , 4 k }, add edges between u and v if
both u , v are 2 k or
exactly one of u , v is k and | u v | is even.
Then
(1) x { x + 2 k if  x 2 k x 2 k + 1 if  2 k < x < 4 k 1 if  x = 4 k
is an isomorphism of G with its complement 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 x 2 k. The map (2) extended by mapping 0 0 is an isomorphism of this new graph G with its complement G ¯ .

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get your answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?