J. Aust. Math. Soc.  76 (2004), 345-356
One-regular cubic graphs of order a small number times a prime or a prime square

Yan-Quan Feng
  Department of Mathematics
  Beijing Jiaotong University
  Beijing 100044
  P.R. China
  yqfeng@center.njtu.edu.cn
and
Jin Ho Kwak
  Department of Mathematics
  Pohang University of Science
  and Technology
  Pohang
  790--784 Korea
  jinkwak@postech.ac.kr


Abstract
A graph is one-regular if its automorphism group acts regularly on the set of its arcs. In this paper we show that there exists a one-regular cubic graph of order $2p$ or $2p^2$ where $p$ is a prime if and only if 3 is a divisor of $p-1$ and the graph has order greater than 25. All of those one-regular cubic graphs are Cayley graphs on dihedral groups and there is only one such graph for each fixed order. Surprisingly, it can be shown that there is no one-regular cubic graph of order $4p$ or $4p^2$.
Download the article in PDF format (size 99 Kb)
TeXAdel Scientific Publishing ©  Australian MS