Constructing an Infinite Family of Cubic 1-Regular Graphs

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 2 p, where p ≥ 13 is a prime congruent to 1 modulo 3. Marušič and Xu [ J. Graph Theory, 25 (1997), 133–138] 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 ≥ 13 is odd such that 3 divides ϕ(n), the Euler function of n. In this paper, we construct an infinite family of cubic 1-regular graphs with order 8(k2 + k + 1)(k ≥ 2) as cyclic-coverings of the three-dimensional Hypercube.