Prove self-complementarity of regular graph with given order.

Question

I am really stuck with the following graph problem:

Prove that for any natural $k\ge1$, there is a self-complementary graph of order $4k+1$ such that it is $2k$-regular.

I have a hint to use induction on k. Although I have found a method of constructing a $2k$-regular graph of order $4(k+1) + 1$ from the $4k+1$ graph, I cannot figure a way to prove it is self-complementary.

What I do for $k+1$ is that I split the k graph, let it be $G$, in 2 groups of $2k$ and $2k+1$ nodes, name them $A$ and $B$ respectively. Then I take a 4 node line graph, name it $H$, and connect its edge nodes to all the nodes of subgraph $B$, and the other 2 inner nodes to the nodes of subgraph $A$. This way, I have a $2k$-regular graph (the degree of every node is $2k+2$) and it is actually a union of 2 self-complementary graphs, $G$ and $H$. I guess I need to prove that this union is self-complementary.

I have spent hours trying to prove it, any help will be appreciated.

Answer 1

It doesn't sound like your procedure will necessarily work. Each of $G$ and $H$ has a node permutation that shows it is self-complementary, but there's nothing in the construction to make sure that when you apply both of them in the combined graph, edges between $G$ and $H$ will map to non-edges and vice versa.

---

Here is an extended hint that I've verified leads to a solution, but it's not by induction (and it's not even clear how to modify it to look like induction) so it's probably not what the problem setter intended for you to find. For all I know, a much simpler solution that I just don't see may be possible.

To explore the problem, I start by drawing down the solution for $k=1$. That is easy because the only possible 2-regular graph of order 5 is the 5-cycle, and it happens to be self-complementary. Then I work out the node permutation that takes this graph to its complement. It turns out to be a 4-cycle plus a node that stays in place. Here is the graph drawn in a way that emphasizes this structure:

    2........
  /         :
1------3    0
     /      :
   4........:

Going to the complement happens by rotating the nodes 1234 cyclically by $90^\circ$ and leaving all the edges in place. Note that the subgraph induced by $\{1,2,3,4\}$ is the 4-line graph which we know to be self-complementary.

My idea is now to construct the graph as consisting of a single node $0$ plus $k$ "layers" that each is a line graph like 2134 above. The central $0$ is connected to $2$ and $4$ of each layer.

The challenge is then to arrange the edges between the layers such that when we rotate all the layers by a quarter-turn, every inter-layer edge turns into a non-edge and vice versa. There's at least one way to do this but I'll leave it to you to puzzle it out.

Answer 2

Here is a simple direct construction of a regular self-complementary graph $G$ of order $4n+1$.

$V(G)=A\cup B\cup C\cup D\cup\{v\}$ where $A,B,C,D$ are disjoint $n$-element sets and $v\notin A\cup B\cup C\cup D$. $$N(v)=A\cup D.$$ $$a\in A\implies N(a)=(A\setminus\{a\})\cup B\cup\{v\}.$$ $$b\in B\implies N(b)=A\cup C.$$ $$c\in C\implies N(c)=B\cup D.$$ $$d\in D\implies N(d)=C\cup(D\setminus\{d\})\cup\{v\}.$$

For an anti-automorphism of $G$ we can take a bijection $\varphi:V(G)\to V(G)$ such that $\varphi(v)=v$, $\varphi(A)=B$, $\varphi(B)=D$, $\varphi(C)=A$, and $\varphi(D)=C$.