Perfect 1-Factorisations of Circulants with Small Degree

  • Sarada Herke
  • Barbara Maenhaut
Keywords: one-factorisation, perfect one-factorisation, circulant graph

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.

Author Biographies

Sarada Herke, The University of Queensland
PhD student, School of Mathematics and Physics
Barbara Maenhaut, The University of Queensland
Lecturer, School of Mathematics and Physics
Published
2013-03-24
Article Number
P58