Constructing an infinite family of cubic 1-regular graphs

Abstract

A graph is 1-regular if its automorphism group acts regularly on the set of its arcs. Miller [J Comb. Theory, B, 10 (1971), 163-182] constructed an infinite family of cubic 1-regular graphs of order 2p, where p 13 is a prime congruent to 1 modulo 3. Marusic and Xu [J Graph Theory, 25 (1997), 133138] found a relation between cubic 1-regular graphs and tetravalent half-transitive graphs with girth 3 and Alspach et al. [J. Aust. Math. Soc. A, 56 (1994), 391-402] constructed infinitely many tetravalent half-transitive graphs with girth 3. Using these results, Miller's construction can be generalized to an infinite family of cubic 1-regular graphs of order 2n, where n greater than or equal to 13 is odd such that 3 divides phi(n), the Euler function of n. In this paper, we construct an infinite family of cubic 1-regular graphs with order 8(k(2) + k + 1) (k greater than or equal to 2) as cyclic-coverings of the three-dimensional Hypercube. (C) 2002 Elsevier Science Ltd. All rights reserved.