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 '18 at 19:43
  • $\begingroup$ @vadim123: Obviously! Why did I thought that the diameter of $C_5$ is $3$?? I feel ashamed! $\endgroup$ – digital-Ink Jan 9 '18 at 21:18
  • 1
    $\begingroup$ One other question is: are there others? $\endgroup$ – Manuel Lafond Jan 10 '18 at 20:13
  • $\begingroup$ I think a large random self-complementary graph is likely to have diameter $2.$ $\endgroup$ – bof Jan 12 '18 at 13:35
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.