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!

Question

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&#039;t know how to develop it. Could you help me? Thanks in advance!

sweetwisdomgw · Accepted Answer

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&#039;t have radius 1 (the fact that the diameter can&#039;t be 1 follows as a corollary). And (excluding the trivial example of a singleton), that can&#039;t happen either, as radius 1 means there is a node which is connected to all other nodes, meaning the complement is not connected.

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

Answered question

Answer & Explanation

New Questions in Descriptive Statistics