Perfect matchings, Hamiltonian cycles and edge-colourings in a class of cubic graphs
Keywords:cubic graph, perfect matching, Hamiltonian cycle, 3-edge-colouring
A graph G has the Perfect-Matching-Hamiltonian property (PMH-property) if for each one of its perfect matchings, there is another perfect matching of G such that the union of the two perfect matchings yields a Hamiltonian cycle of G. The study of graphs that have the PMH-property, initiated in the 1970s by Las Vergnas and Häggkvist, combines three well-studied properties of graphs, namely matchings, Hamiltonicity and edge-colourings. In this work, we study these concepts for cubic graphs in an attempt to characterise those cubic graphs for which every perfect matching corresponds to one of the colours of a proper 3-edge-colouring of the graph. We discuss that this is equivalent to saying that such graphs are even-2-factorable (E2F), that is, all 2-factors of the graph contain only even cycles. The case for bipartite cubic graphs is trivial, since if G is bipartite then it is E2F. Thus, we restrict our attention to non-bipartite cubic graphs. A sufficient, but not necessary, condition for a cubic graph to be E2F is that it has the PMH-property. The aim of this work is to introduce an infinite family of E2F non-bipartite cubic graphs on two parameters, which we coin papillon graphs, and determine the values of the respective parameters for which these graphs have the PMH-property or are just E2F. We also show that no two papillon graphs with different parameters are isomorphic.
Articles in this journal are published under Creative Commons Attribution 4.0 International License