How many self-complementary simple graphs are there on $n$ vertices, up to isomorphism? Denoting this by $S(n)$, it is clear that $S(n)=0$ unless $|K_n|=\frac{n(n-1)}2$ is even, which is when $n=4k$ or $4k+1$. For an upper bound, the number of graphs with $\frac{n(n-1)}4$ edges is ${n(n-1)/2\choose n(n-1)/4}$, and for each self-complementary graph, its complement is also self-complementary, so $S(n)\le\frac12\!{n(n-1)/2\choose n(n-1)/4}$. Are there any better bounds on this number? Are there any estimates for $O(S(n))$?

For a lower bound, we can use the four-path addition operation described in Constructing self-complementary graphs, which works by taking a given self-complementary graph $G$, and adding four vertices in a path $v_1-v_2-v_3-v_4$, where $v_2$ and $v_3$ are also connected to every vertex in $G$. The new graph $G'$ is also self-complementary, and since every vertex in $G$ has degree $\ge2$ in $G'$, $v_1$ and $v_4$ can be identified as the only vertices of degree $1$, and $v_2$ and $v_3$ are identified as being connected to the other two. Thus $G$ is identifiable from $G'$, so two non-isomorphic self-complementary graphs yield non-isomorphic extensions.

Furthermore, there is a second construction similar to the above where every point in $G$ is connected to $v_1$ and $v_4$ instead. This construction yields no degree $1$ vertices as long as $n\ge1$, so it is distinct from any result of the first construction. However, since there are no distinguishable vertices here (there are two degree $2$ vertices, but any isolated point in $G$ will also have degree $2$ in $G'$), so we can only guarantee one extra graph. Thus $S(n)\ge S(n-4)+1$ for $n>0$, and since $S(0)=S(1)=S(4)=1$, we have $S(n)\ge\frac n4$ when $n\bmod 4\in\{0,1\}$.


Does "degree" in your title means "number of vertices"? It seems to be, given the drift of your question. Self-complementary graphs were enumerated by Read and later by Clapham in "An easier enumeration of self-complementary graphs" in Proc.Edinburgh Math Soc. (1984) 27, 181-183. The formula is a sum over cycle-types of permutations, I am not going to try to reproduce it here.

There is a paper by Palmer "Asymptotic formulas for the number of self-complementary graphs and digraphs" in Mathematika (1970). According to the review on mathscinet, he shows that the number of self-complementary graphs on $4n$ vertices is asymptotic to $$ \frac{2^{2n^2−2n}}{n!} (1+n(n−1)2^{5−4n} + O(n^3/2^{6n})). $$

  • $\begingroup$ Yes, the "degree" in the title was a slip of the tongue. (Is there a name for the number of vertices of a graph, akin to "order" for groups?) Thanks for the reference! That's a much tighter bound than I was expecting. By the way, isn't $n^3/6n$ just $n^2/6$? $\endgroup$ – Mario Carneiro Apr 26 '14 at 22:12
  • $\begingroup$ Some people use order for the number of vertices and size for the number of edges, but I can never keep those terms straight. I just write graphs on $n$ vertices. Your query about the $n^3/6$ arise because I made a mistake transcribing the formula, which I think is now fixed. $\endgroup$ – Chris Godsil Apr 26 '14 at 22:42

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.