0
$\begingroup$

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\}$.

$\endgroup$

1 Answer 1

4
$\begingroup$

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})). $$

$\endgroup$
2
  • $\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$ Apr 26, 2014 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$ Apr 26, 2014 at 22:42

You must log in to answer this question.

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