**Updates and Correspondence**

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*

My snail mail address is:

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, *s*^{3} 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. Zametki***35**
(1984) 251--262. (English translation) *Math. Notes***35** (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 4*k*+1 vertices

and degree 2*k*, while regular self-complementary digraphs have
2*k*+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.

Home page: www.AlastairFarrugia.net

This page: www.AlastairFarrugia.net/sc-graph/updates.html