Perfect 1-Factorisations of Circulants with Small Degree

Abstract

A $1$-factorisation of a graph $G$ is a decomposition of $G$ into edge-disjoint $1$-factors (perfect matchings), and a perfect $1$-factorisation is a $1$-factorisation in which the union of any two of the $1$-factors is a Hamilton cycle.  We consider the problem of the existence of perfect $1$-factorisations of even order circulant graphs with small degree.  In particular, we characterise the $3$-regular circulant graphs that admit a perfect $1$-factorisation and we solve the existence problem for a large family of $4$-regular circulants.  Results of computer searches for perfect  $1$-factorisations of $4$-regular circulant graphs of orders up to $30$ are provided and some problems are posed.