Perfect 1-factorisations of circulants with small degree (Q1953445)

Summary: 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.