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: