Perfect 1-Factorisations of Circulants with Small Degree
| Autor: | Sarada Herke, Barbara Maenhaut |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
Discrete mathematics
Perfect power Applied Mathematics Strong perfect graph theorem Theoretical Computer Science Combinatorics Computational Theory and Mathematics Chordal graph Trivially perfect graph Perfect graph Unitary perfect number Discrete Mathematics and Combinatorics Perfect graph theorem Cograph Geometry and Topology Mathematics |
| Zdroj: | The Electronic Journal of Combinatorics. 20 |
| ISSN: | 1077-8926 |
| DOI: | 10.37236/2264 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|