Séminaire Lotharingien de Combinatoire, B36d (1996), 36pp.
Mikhail Klin, Valery Liskovets and Reinhard Pöschel
Analytical Enumeration of Circulant Graphs
with Prime-Squared
Number of Vertices.
Abstract.
A method for the analytical enumeration of circulant graphs with p2 vertices,
p a prime, is proposed and described in detail. It is based on the use of
S-rings and Pólya's enumeration technique. Two different approaches,
"structural" and "multiplier", are developed and compared. As a result,
we get counting formulae and generating functions (by valency) for
non-isomorphic p2-vertex directed and undirected circulant graphs
as well as for some subclasses of them such as tournaments
and self-complementary
graphs. These are the first general enumerative results for circulant graphs
for which the so-called Ádám (single-multiplier)
isomorphism condition does not hold. Some numerical data and interrelations
between formulae are also obtained. The first expository part of the
paper may serve as a self-contained introduction to the use of Schur rings for
enumeration.
The following version is available: