Infinitely many one-regular Cayley graphs on dihedral groups of any prescribed valency

Abstract

A graph is one-regular if its automorphism group acts regularly on the arc set. In this paper, we construct a new infinite family of one-regular Cayley graphs of any prescribed valency. In fact, for any two positive integers l, k >= 2 except for (l, k) is an element of {(2, 3), (2, 4)}, the Cayley graph Cay(D-n, S) on dihedral groups D-n = < a, b vertical bar a(n) = b(2) = (ab)(2) = 1 > with S = {a(1+l+center dot center dot center dot+l1)b vertical bar 0 <= t <= k - 1} and n = Sigma(k-1)(j=0) l(j) is one- regular. All of these graphs have cyclic vertex stabilizers and girth 6. As a continuation of Nlarugi6 and Pisanski&apos;s classification of cubic one-regular Cayley graphs on dihedral groups in [D. Marusic, T. Pisanski, Symmetries of hexagonal graphs on the torus, Croat. Chemica Acta 73 (2000) 969-981], the 5-valent one-regular Cayley graphs on dihedral groups are classified. Also, with only finitely many possible exceptions, all of one-regular Cayley graphs on dihedral groups of any prescribed prime valency are constructed. (c) 2007 Elsevier Inc. All rights reserved.