Abstract | ||
---|---|---|
It is proven that for any integer g≥0 and k∈{0,…,10}, there exist infinitely many 5-regular graphs of genus g containing a 1-factorisation with exactly k pairs of 1-factors that are perfect, i.e. form a hamiltonian cycle. For g=0 and k=10, this settles a problem of Kotzig from 1964. Motivated by Kotzig and Labelle's “marriage” operation, we discuss two gluing techniques aimed at producing graphs of high cyclic edge-connectivity. We prove that there exist infinitely many planar 5-connected 5-regular graphs in which every 1-factorisation has zero perfect pairs. On the other hand, by the Four Colour Theorem and a result of Brinkmann and the first author, every planar 4-connected 5-regular graph satisfying a condition on its hamiltonian cycles has a linear number of 1-factorisations each containing at least one perfect pair. We also prove that every planar 5-connected 5-regular graph satisfying a stronger condition contains a 1-factorisation with at most nine perfect pairs, whence, every such graph admitting a 1-factorisation with ten perfect pairs has at least two edge-Kempe equivalence classes. |
Year | DOI | Venue |
---|---|---|
2022 | 10.1016/j.jctb.2021.12.008 | Journal of Combinatorial Theory, Series B |
Keywords | DocType | Volume |
Planar,Regular,1-factor,Edge-colouring,Hamiltonian | Journal | 154 |
ISSN | Citations | PageRank |
0095-8956 | 0 | 0.34 |
References | Authors | |
0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Nico Van Cleemput | 1 | 16 | 6.31 |
Carol T. Zamfirescu | 2 | 38 | 15.25 |