Perfect 1-factorizations of a family of Cayley graphs

Sarada Herke, Barbara Maenhaut

Research output: Contribution to journalArticleResearchpeer-review

2 Citations (Scopus)


A 1-factorization of a graph G is a decomposition of G into edge-disjoint 1-factors (perfect matchings), and a perfect 1-factorization is a 1-factorization 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-factorizations of even order 4-regular Cayley graphs, with a particular interest in circulant graphs. In this paper, we study a new family of graphs, denoted Dh,k, which are Cayley graphs if and only if k is even or h = 2. By solving the perfect 1-factorization problem for a large class of Dh,k graphs, we obtain a new class of 4-regular bipartite circulant graphs that do not have a perfect 1-factorization, answering a problem posed in [7]. With further study of Dh,k graphs, we prove the nonexistence of P1Fs in a class of 4-regular non-bipartite circulant graphs, which is further support for a conjecture made in [7].
Original languageEnglish
Pages (from-to)369-399
Number of pages31
JournalJournal of Combinatorial Designs
Issue number9
Publication statusPublished - 2015


  • 1-factorization
  • Cayley graph
  • perfect 1-factorization

Cite this