3
$\begingroup$

It is known (and not so hard to prove) that any self-complementary graph with more than one vertex has diameter $2$ or $3$.

What would be the simplest example (i.e., with the least number of vertices) of a self-complementary graph of diameter $2$?

Edit: As pointed out in the comments, $C_5$ is the answer to the question. What would be the next self-complementary graph with diameter 2?

$\endgroup$
4
  • 4
    $\begingroup$ How about $C_5$? $\endgroup$
    – vadim123
    Jan 9, 2018 at 19:43
  • $\begingroup$ @vadim123: Obviously! Why did I thought that the diameter of $C_5$ is $3$?? I feel ashamed! $\endgroup$ Jan 9, 2018 at 21:18
  • 1
    $\begingroup$ One other question is: are there others? $\endgroup$ Jan 10, 2018 at 20:13
  • $\begingroup$ I think a large random self-complementary graph is likely to have diameter $2.$ $\endgroup$
    – bof
    Jan 12, 2018 at 13:35

2 Answers 2

5
$\begingroup$

For any $n\in\mathbb N,$ here's how you can construct a self-complementary graph of diameter $2$ and order $4n+1.$

Choose a graph $G$ of order $n.$

Start with a $C_5$ graph, with vertices $A,B,C,D,E$ and edges $AB,BC,CD,DE,EA.$

Replace each of the vertices $B$ and $E$ with a copy of $G,$ and replace each of the vertices $C$ and $D$ with a copy of the complementary graph $\overline G.$

More precisely: The graph has vertex set $A\cup B\cup C\cup D\cup E$ where $A,B,C,D,E$ are disjoint sets and $|A|=1$ and $|B|=|C|=|D|=|E|=n.$ The induced subgraphs on $B$ and $E$ are isomorphic to $G,$ the induced subgraphs on $C$ and $D$ are isomorphic to $\overline G.$ There are edges joining all vertices in $A$ to all vertices in $B,$ all vertices in $B$ to all vertices in $C,$ all vertices in $C$ to all vertices in $D,$ all vertices in $D$ to all vertices in $E,$ and all vertices in $E$ to all vertices in $A.$ On the other hand, there are no edges between $A$ and $C,$ or between $C$ and $E,$ or between $E$ and $B,$ or between $B$ and $D,$ or between $D$ and $A.$

In other words: Just use the most obvious construction of a self-complementary graph of order $4n+1.$

Example: For $G=K_2$ it looks like

$\endgroup$
0
2
$\begingroup$

In my previous answer I showed how to construct self-complementary graphs of diameter $2$ and order $4n+1$ for every $n\in\mathbb N.$ (In a similar way we can construct self-complementary graphs of diameter $3$ and orders $4n$ and $4n+1$ for every $n\in\mathbb N.$) In this answer I sketch a non-constructive proof of the fact that self-complementary graphs of diameter $2$ and order $4n$ exist for all sufficiently large $n.$

Let $K_{4n}=(V,E).$ Partition $V$ into $4$-element sets $V_1,\dots,V_n.$ Choose a permutation $\pi$ of $V$ which permutes each $V_i$ cyclically. Let $\pi'$ be the corresponding permutation of $E,$ which maps an edge $xy$ to the edge $\pi(x)\pi(y).$ We will get a self-complementary graph on the vertex set $V$ by coloring each edge black or white, so that $\pi'$ maps black edges to white edges and vice versa; then $\pi$ is an isomorphism from the black graph to the white graph.

Because of the cycle structure of $\pi,$ all cycles of $\pi'$ have even length, in fact, length $2$ or $4.$ (WARNING: we are using the word "cycle" in the permutation group sense, not the graph theory sense.) Therefore, we can get a self-complementary graph by coloring the edges of each cycle of $\pi'$ alternately black and white.

There are two ways to color each cycle. Let's randomize the process by letting an independent fair coin toss determine the coloring of each cycle. Let $p_n$ be the probability that the resulting self-complementary graph will have diameter greater than $2.$ It is pretty clear that $p_n\to0$ as $n\to\infty;$ my crude estimate is $p_n\le\frac12(\frac34)^{n-2}\binom{4n}2.$ Hence for sufficiently large $n$ we have $p_n\lt1$ which means that are self-complementary graphs of diameter $2.$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .