Perfect 1-Factorizations of a Family of Cayley Graphs
| Autor: | Barbara Maenhaut, Sarada Herke |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
Discrete mathematics
Clique-sum 010102 general mathematics Strong perfect graph theorem 0102 computer and information sciences 01 natural sciences Combinatorics Indifference graph Pathwidth 010201 computation theory & mathematics Trivially perfect graph Chordal graph Discrete Mathematics and Combinatorics Cograph Split graph 0101 mathematics Mathematics |
| Zdroj: | Journal of Combinatorial Designs. 23:369-399 |
| ISSN: | 1063-8539 |
| DOI: | 10.1002/jcd.21399 |
| Popis: | 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 D h,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 D h,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 D h,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]. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text