ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P3.01
https://doi.org/10.26493/1855-3974.2672.73b
(Also available at http://amc-journal.eu)
Perfect matchings, Hamiltonian cycles and
edge-colourings in a class of cubic graphs
Marién Abreu
Dipartimento di Matematica, Informatica ed Economia,
Università degli Studi della Basilicata, Italy
John Baptist Gauci *
Department of Mathematics, University of Malta, Malta
Domenico Labbate , Federico Romaniello
Dipartimento di Matematica, Informatica ed Economia,
Università degli Studi della Basilicata, Italy
Jean Paul Zerafa †
Department of Technology and Entrepreneurship Education,
University of Malta, Malta and
Department of Computer Science, Faculty of Mathematics, Physics and Informatics
Comenius University, Mlynská Dolina, 842 48 Bratislava, Slovakia
Received 16 July 2021, accepted 25 August 2022, published online 6 January 2023
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ä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
*Corresponding author.
†The author was partially supported by VEGA 1/0743/21, VEGA 1/0727/22, and APVV-19-0308.
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
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.
Keywords: Cubic graph, perfect matching, Hamiltonian cycle, 3-edge-colouring.
Math. Subj. Class. (2020): 05C15, 05C45, 05C70
E-mail addresses: marien.abreu@unibas.it (Marién Abreu), john-baptist.gauci@um.edu.mt (John Baptist
Gauci), domenico.labbate@unibas.it (Domenico Labbate), federico.romaniello@unibas.it (Federico
Romaniello), zerafa.jp@gmail.com (Jean Paul Zerafa)
ISSN 1855-3966 (tiskana izd.), ISSN 1855-3974 (elektronska izd.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P3.01
https://doi.org/10.26493/1855-3974.2672.73b
(Dostopno tudi na http://amc-journal.eu)
Popolna prirejanja, hamiltonski cikli in barvanja
povezav v družini kubičnih grafov
Marién Abreu
Dipartimento di Matematica, Informatica ed Economia,
Università degli Studi della Basilicata, Italy
John Baptist Gauci *
Department of Mathematics, University of Malta, Malta
Domenico Labbate , Federico Romaniello
Dipartimento di Matematica, Informatica ed Economia,
Università degli Studi della Basilicata, Italy
Jean Paul Zerafa †
Department of Technology and Entrepreneurship Education,
University of Malta, Malta and
Department of Computer Science, Faculty of Mathematics, Physics and Informatics
Comenius University, Mlynská Dolina, 842 48 Bratislava, Slovakia
Prejeto 16. julija 2021, sprejeto 25. avgusta 2022, objavljeno na spletu 6. januarja 2023
Povzetek
Graf G ima lastnost hamiltonskih popolnih prirejanj (je tipa PMH), če za vsako izmed
njegovih popolnih prirejanj obstaja neko drugo popolno prirejanje v grafu G, tako da unija
teh dveh popolnih prirejanj da hamiltonski cikel grafa G. Raziskovanje takšnih grafov sta
začela v 1970ih Las Vergnas in Häggkvist; predstavlja kombinacijo treh dobro raziskanih
pojmov v zvezi z grafi, in sicer prirejanj, hamiltonskih ciklov ter barvanj povezav. V tem
delu raziskujemo te koncepte za kubične grafe v želji, da bi karakterizirali tiste kubične
grafe, za katere vsako popolno prirejanje ustreza eni od barv pravilnega 3-barvanja povezav
grafa. Ugotavljamo, da je to enakovredno trditvi, da so taki grafi sodo-2-faktorizabilni
(E2F), kar pomeni, da vsi 2-faktorji grafa vsebujejo samo sode cikle. Primer dvodelnih
kubičnih grafov je trivialen, saj če je graf G dvodelen, potem je tudi tipa E2F. Zato svojo
pozornost omejimo na nedvodelne kubične grafe. Zadosten, vendar ne potreben pogoj, da
je kubični graf tipa E2F, je, da je tipa PMH. Namen tega dela je predstaviti neskončno
*Kontaktni avtor.
†Avtor je bil delno podprt s strani VEGA 1/0743/21, VEGA 1/0727/22 in APVV-19-0308.
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/4.0/
družino nedvodelnih kubičnih grafov tipa E2F z dvema parametroma, ki smo jih poime-
novali metuljasti grafi, in določiti vrednosti ustreznih parametrov, za katere so ti grafi tipa
PMH ali pa so kar tipa E2F. Prav tako dokažemo, da nobena dva metuljasta grafa z različ-
nimi vrednostmi parametrov nista izomorfna.
Ključne besede: Kubični grafi, popolna prirejanja, hamiltonski cikel, 3-barvanje povezav.
Math. Subj. Class. (2020): 05C15, 05C45, 05C70
E-poštni naslovi: marien.abreu@unibas.it (Marién Abreu), john-baptist.gauci@um.edu.mt (John Baptist
Gauci), domenico.labbate@unibas.it (Domenico Labbate), federico.romaniello@unibas.it (Federico
Romaniello), zerafa.jp@gmail.com (Jean Paul Zerafa)