{
  "id": "2106.00513",
  "version": "v1",
  "published": "2021-06-01T14:17:05.000Z",
  "updated": "2021-06-01T14:17:05.000Z",
  "title": "Papillon graphs: perfect matchings, Hamiltonian cycles and edge-colourings in cubic graphs",
  "authors": [
    "Marién Abreu",
    "John Baptist Gauci",
    "Domenico Labbate",
    "Federico Romaniello",
    "Jean Paul Zerafa"
  ],
  "comment": "18 pages, 11 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "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\\\"{a}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 two infinite families of non-bipartite cubic graphs, which we term papillon graphs and unbalanced papillon graphs, and determine the values of their respective parameters for which these graphs have the PMH-property or are just E2F.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-06-01T14:17:05.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C45",
      "05C70"
    ],
    "keywords": [
      "hamiltonian cycle",
      "non-bipartite cubic graphs",
      "edge-colourings",
      "pmh-property",
      "perfect matchings yields"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}