Prove that a self-complementary graph has radius 2 and diameter 2 or 3 if G ~= bar G, then both graphs G and bar G are connected, and that, for any graph, if rad(G)>=3 then rad(bar G)<=2, and that if diam(G)>=3 then diam(bar G)<=3, should make the proof quite easier

Lexi Mcneil

Lexi Mcneil

Answered question

2022-07-21

Prove that a self-complementary graph has radius 2 and diameter 2 or 3.
I think that is one of the well-known properties of self-complementary graphs, but I am having some troubles trying to prove it. The facts that, if G G ¯ , then both graphs G and G ¯ are connected, and that, for any graph, if r a d ( G ) 3 then r a d ( G ¯ ) 2, and that if d i a m ( G ) 3 then d i a m ( G ¯ ) 3, should make the proof quite easier, but I don't know how to develop it. Could you help me? Thanks in advance!

Answer & Explanation

sweetwisdomgw

sweetwisdomgw

Beginner2022-07-22Added 20 answers

The properties you list directly imply that a self-complementary graph cannot have radius 3 or higher, and it cannot have diameter 4 or higher.
The only thing that remains to show is that it can't have radius 1 (the fact that the diameter can't be 1 follows as a corollary). And (excluding the trivial example of a singleton), that can't happen either, as radius 1 means there is a node which is connected to all other nodes, meaning the complement is not connected.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

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

Didn't find what you were looking for?