One-regular graphs of square-free order of prime valency

A graph is one-regular if its automorphism group acts regularly on the set of arcs of the graph. Marušič and Pisanski [D. Marušič and T. Pisanski, Symmetries of hexagonal graphs on the torus, Croat. Chemica Acta 73 (2000) 969–981] classified one-regular Cayley graphs on a dihedral group of valency 3, and Kwak et al. [J.H. Kwak, Y.S. Kwon, J.M. Oh, Infinitely many one-regular Cayley graphs on dihedral groups of any prescribed valency, J. Combin. Theory B 98 (2008) 585–598] classified those of valency 5. In this paper one-regular Cayley graphs on a dihedral group of any prime valency are classified and enumerated. It is shown that for an odd prime qq, there exists a qq-valent one-regular Cayley graph on the dihedral group of order 2m2m if and only if m=qtp1e1p2e2⋯pses≥13, where t≤1t≤1, s≥1s≥1, ei≥1ei≥1 and pipi’s are distinct primes such that q∣(pi−1)q∣(pi−1). There are exactly (q−1)s−1(q−1)s−1 non-isomorphic such graphs for a given order. Consequently, one-regular cyclic Haar graphs of prime valency are classified and enumerated. Furthermore, it is shown that every qq-valent one-regular graph of square-free order is a Cayley graph on a dihedral group, and as a result, qq-valent one-regular graphs of square-free order are classified and enumerated.