Perfect 1‐Factorizations of a Family of Cayley Graphs |
| |
Authors: | Sarada Herke Barbara Maenhaut |
| |
Institution: | 1. School of Mathematical Sciences, Monash University, Clayton, VIC, Australia;2. School of Mathematics and Physics, The University of Queensland, QLD, Australia |
| |
Abstract: | 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 , which are Cayley graphs if and only if k is even or . By solving the perfect 1‐factorization problem for a large class of 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 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 . |
| |
Keywords: | 1‐factorization Cayley graph perfect 1‐factorization |
|
|