Self-complementary graphs and generalizations

Updating and improving the survey would take a lot of time and effort, so I will not be making any substantial updates. This page lists those typos, omissions and mistakes that have come to my attention, as well as (in bold) some new results or solutions to what had been open problems; however, this is not a comprehensive list.

If you know of any further results or papers not listed in the manual, or have any queries, comments or suggestions, please contact me at info@AlastairFarrugia.net

Alastair Farrugia
Dept. of Mathematics
Faculty of Science
University of Malta
Msida MSD 2080
Malta

Theorem 0.14, which was joint work with B.R. Nair and A. Vijayakumar, is actually a special case of a result proved much earlier by W. Imrich [Thm. 9.4, Assoziative Produkte von Graphen, Österreich. Akad. Wiss. Math.-Natur. Kl. S.-B. II 180 (1972), 203--239]:- the lexicographic product of G and H is vertex transitive if and only if G and H are both vertex transitive. So Nair and Vijayakumar's claim [Strongly edge triangle regular graphs and a conjecture of Kotzig, Discrete Math.158 (1996) 201--209. MR 97d:05283.] to have an infinite family of counterexamples to Kotzig's conjecture was correct all along - it is re-stated in slightly stronger form in Thm. 0.15 in the manual.

Thm. 1.30.E is due not only to Gibbs but also to Salvi-Zagaglia [Grafi autocomplementari e grafi auto-opposti (Self-complementary and self-converse graphs),  Istit. Lombardo Accad. Sci. Lett. Rend. A 111 (1977) 163 -- 172. MR 58:21775.]

The problems in 1.56 have been partially answered. There exist infinitely many pairs of co-spectral self-complementary graphs which are also co-spectral to non-self-complementary graphs; and there exist arbitrarily large sets of graphs which are all co-spectral. A handful of co-spectral graphs, not all of them self-complementary, were presented by Godsil, Holton and McKay [The spectrum of a graph,  Combinatorial mathematics, V (Proc. Fifth Austral. Conf., Roy. Melbourne Inst. Tech., Melbourne, 1976) 91--117. Lecture Notes in Math 622 (1977) Springer, Berlin. MR 58:27642.] The constructions for the infinite sets is joint work with Chris Godsil, and will be presented in a paper currently in preparation.

In 1.72, the degrees of G[odd] and G[even] should be r-k and 3k-1-r, respectively. This also corrects the claim in Wojda and Zwonek [Coloring edges of self-complementary graphs, Discrete Appl. Math. 79 (1997) 279--284. MR 98f:05069] that both of these subgraphs have even degrees.
The results of 1.71 and 1.72 are both corollaries of Theorem 5 of Kotzing [1-factorizations of Cartesian products of regular graphs, J. Graph Theory 3 (1979) 23--34. MR 80c:05115]; using Kotzig's ideas allows for a slightly simpler proof.

Proposition 3.5 can be strengthened to read "A connected arc-transitive digraph D on at least 3 vertices is vertex-transitive".

In 3.41 we mentioned briefly a graph produced by Xu [A counterexample to an open problem of A. Kotzig concerning self-complementary graphs, (Chinese), Acta Math. Appl. Sinica 14 (1991) 125--127. MR 96b:05096.] Xu's graph actually does not solve Kotzig's problem ("Do all regular sc-graphs have an antimorphism with cycles only of lengths 4 and 1?"). Although it has an antimorphism s with a cycle of length 1 and another of length 12, s3 is also an antimorphism of the graph. By contrast, Hartsfield's graph [On regular self-complementary graphs,  J. Graph Theory 11 (1987) 537--538] was a suitable counterexample as its antimorphisms all have three cycles, of lengths 1,4,8.

Problem 3.44.A(1) has been solved -- vertex-transitive self-complementary graphs on n vertices exist if and only if n is the sum of two squares. The "if" part is due to Rao, and is discussed in 3.16 in the manual. The "only if" was established recently by Muzychuk [On Sylow subgraphs of vertex-transitive self-complementary graphs, Bull. London Math. Soc. 31 (1999), no. 5, 531--533. MR 2000i:05093. CMP 1 703 877 (99:16).]

There is a typo in 3.44.A(2) -- "strongly regular graphs" should read "strongly regular sc-graphs".

Problem 3.44.B(2) has also been solved (Valery Liskovets - private communication). Mixed sc-circulants (i.e. circulant sc-digraphs which are neither graphs nor tournaments) do exist. One easy construction is to take the product X(Y) of two self-complementary circulants X and Y, so long as X and Y are not both tournaments and not both graphs. By taking X to be a circulant sc-graph on x vertices, and Y a circulant sc-tournament on y vertices, we obtain mixed sc-circulants on xy vertices, for any x with prime divisors all congruent to 1 (mod 4), and any odd y. There are 4 mixed sc-circulants on 15 vertices, having connection sets S = {1,-2,3,-3, 4,5,7}, {1,-2,3,-3,4,-5,7}, {1,-1,4,-4,5,6,-6} and {1,-1,4,-4,-5,6,-6}. These are not undirected graphs (since S and -S are different in each case) and not tournaments (since S and -S are not disjoint). Multiplying by a number prime to 15 defines an isomorphism; multiplying by 2 clearly transforms each graph to its complement, so they are self-complementary.

Problem 3.44 (D) has been solved by Cai Heng Li and Cheryl A. Praeger (Self-complementary vertex-transitive graphs need not be Cayley graphs, Bull. London Math. Soc, to appear). Their paper gives an infinite class of vertex-transitive sc-graphs that are not Cayley graphs.

Colbourn and Colbourn [Isomorphism problems involving self-complementary graphs and tournaments, in Proc. Eighth Manitoba Conference on Numerical Math. and Computing (Univ. Manitoba, 1978), Utilitas Math., Winnipeg, Congr . Numer. 12 (1979) 153--164. MR 81c:05082] proved that the isomorphism problem for graphs is polynomially equivalent to both the recognition and the isomorphism problem for self-complementary graphs. They stated that analogous results hold for digraphs and regular self-complementary digraphs, or tournaments and regular self-complementary tournaments. These additional results were not reported in the survey (paragraphs 4.2 - 4.10) because there was a problem with their construction, but this can be patched up; the correct version should appear in a paper currently in preparation.

At the end of the proof of Thm. 5.6, there are three references to F(G) which should read F(D). Also, it should be specified for clarity that $\tau$ is some antimorphism, and $\alpha$ some automorphism.

Reference 314 was incorrectly attributed; its author is actually K. Reidemeister.

Some corrections and comments regarding enumeration

A paper by Xu and Li [Enumeration of labeled self-complementary graphs, (Chinese), Pure Appl. Math. 9 (1993) 67--76. MR 94i:05043] reports the number of labelled sc-graphs with 4, 5, 8 and 9 vertices as 12, 72, 112,140 and  4,627,224, respectively.  The values for n = 4 and 5 are quickly checked, but Ambrosimov [An asymptotic formula for the number of self-complementary labeled graphs, (Russian), Mat. Zametki35 (1984) 251--262. (English translation) Math. Notes35 (1984) 132--139. MR 85d:05130] reports an asymptotic formula whose values for n = 4, 5, 8 and 9 are 13, 118, 166,346 and 5,734,688, respectively, which seems inconsistent with the previous paper.

Another anomaly with an asymptotic formula arose in a paper by Sridharan [Asymptotic formula for the number of self-converse digraphs, in Proc. Symposium on Graph Theory (Indian Statist. Inst., Calcutta, 1976), MacMillan, India, ISI Lecture Notes 4 (1979) 299--304. MR 81c:05044], who approximated the number of self-converse oriented graphs. Palmer pointed out an error in his review, and showed that the formula for n = 20 is already too low by a factor of at least 10^10. An asymptotic estimate for these graphs was later given by Robinson [Asymptotic number of self-converse digraphs, announced].

Colbourn and Colbourn [Isomorphism problems involving self-complementary graphs and tournaments, in Proc. Eighth Manitoba Conference on Numerical Math. and Computing (Univ. Manitoba, 1978), Utilitas Math., Winnipeg, Congr. Numer. 12 (1979) 153--164. MR 81c:05082] asked for the number of regular sc-graphs and sc-digraphs. Parthasarathy and Sridharan [Enumeration of self-complementary graphs and digraphs, J. Math. Phys. Sci. 3 (1969) 410--414. MR 41:8308] gave formulas which count self-complementary graphs and digraphs according to their degree sequence. It would probably not be difficult to use these to answer Colbourn and Colbourn's question, since regular self-complementary graphs must have 4k+1 vertices
and degree 2k, while regular self-complementary digraphs have 2k+1 vertices and degree k, so in each case there is only one degree sequence to consider. There is as yet no counting formula, however, for strongly regular sc-graphs.

Written on: 31st October, 1999.
Last updated: 12th December, 2007.