Regular Cayley maps for finite abelian groups

A regular Cayley map for a finite group A is an orientable map whose orientation-preserving automorphism group G acts regularly on the directed edge set and has a subgroup isomorphic to A that acts regularly on the vertex set. This paper considers the problem of determining which abelian groups have regular Cayley maps. The analysis is purely algebraic, involving the structure of the canonical form for A. The case when A is normal in G involves the relationship between the rank of A and the exponent of the automorphism group of A, and the general case uses Ito's theorem to analyze the factorization G = AY, where Y is the (cyclic) stabilizer of a vertex. Supported in part by the N.Z. Marsden Fund (grant no. UOA0124).     

On the excess of vertex-transitive graphs of given degree and girth

We consider a restriction of the well-known Cage Problem to the class of vertex-transitive graphs, and consider the problem of finding the smallest vertex-transitive $k$-regular graphs of girth $g$. Counting cycles to obtain necessary arithmetic conditions on the parameters $(k,g)$, we extend previous results of Biggs, and prove that, for any given excess $e$ and any given degree $k\ge 4$, the asymptotic density of the set of girths $g$ for which there exists a vertex-transitive $(k,g)$-cage with excess not exceeding $e$ is 0.     

Constructions of Self-complementary Circulants with No Multiplicative Isomorphisms

The main topic of the paper is the question of the existence of self-complementary Cayley graphs Cay(G, S) with the property S^σ ≠ = G^# \ S for all σ Aut(G). We answer this question in the positive by constructing an infinite family of self-complementary circulants with this property. Moreover, we obtain a complete classification of primes p for which there exist self-complementary circulants of order p²with this property.     

Biregular Cages of Odd Girth

Biregular ‐cages are graphs of girth g that contain vertices of degrees r and m and are of the smallest order among all such graphs. We show that for every and every odd , there exists an integer m₀ such that for every even , the biregular ‐cage is of order equal to a natural lower bound analogous to the well‐known Moore bound. In addition, when r is odd, the restriction on the parity of m can be removed, and there exists an integer m₀ such that a biregular ‐cage of order equal to this lower bound exists for all . This is in stark contrast to the result classifying all cages of degree k and girth g whose order is equal to the Moore bound.     

Embedding arbitrary finite simple graphs into small strongly regular graphs

It is well known that any finite simple graph Γ is an induced subgraph of some exponentially larger strongly regular graph Γ (e.g., [2, 8]). No general polynomial‐size construction has been known. For a given finite simple graph Γ on υ vertices, we present a construction of a strongly regular graph Γ on O(υ⁴) vertices that contains Γ as its induced subgraph. A discussion is included of the size of the smallest possible strongly regular graph with this property. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 1–8, 2000     

Recursive constructions of small regular graphs of given degree and girth

We revisit and generalize a recursive construction due to Sachs involving two graphs which increases the girth of one graph and the degree of the other. We investigate the properties of the resulting graphs in the context of cages and construct families of small graphs using geometric graphs, Paley graphs, and techniques from the theory of Cayley maps.     

On a Construction of Infinite Families of Regular Cayley Maps

Received: February 28, 1995