Perfect 1-Factorisations of Circulants with Small Degree
Keywords: one-factorisation, perfect one-factorisation, circulant graph
AbstractA $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.