Geodesic
Perfect matchings, Hamiltonian cycles and edge-colourings in a class of cubic graphs
Ars Mathematica Contemporanea, Tome 23 (2023) no. 3, article no. 01, 18 p.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

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.
DOI : 10.26493/1855-3974.2672.73b
Keywords: cubic graph, perfect matching, Hamiltonian cycle, 3-edge-colouring 
@article{10_26493_1855_3974_2672_73b,
     author = {Mari\'en Abreu and John Baptist Gauci and Domenico Labbate and Federico Romaniello and Jean Paul Zerafa},
     title = {Perfect matchings, {Hamiltonian} cycles and edge-colourings in a class of cubic graphs},
     journal = {Ars Mathematica Contemporanea},
     eid = {01},
     publisher = {mathdoc},
     volume = {23},
     number = {3},
     year = {2023},
     doi = {10.26493/1855-3974.2672.73b},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2672.73b/}
}
TY  - JOUR
AU  - Marién Abreu
AU  - John Baptist Gauci
AU  - Domenico Labbate
AU  - Federico Romaniello
AU  - Jean Paul Zerafa
TI  - Perfect matchings, Hamiltonian cycles and edge-colourings in a class of cubic graphs
JO  - Ars Mathematica Contemporanea
PY  - 2023
VL  - 23
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2672.73b/
DO  - 10.26493/1855-3974.2672.73b
LA  - en
ID  - 10_26493_1855_3974_2672_73b
ER  - 
%0 Journal Article
%A Marién Abreu
%A John Baptist Gauci
%A Domenico Labbate
%A Federico Romaniello
%A Jean Paul Zerafa
%T Perfect matchings, Hamiltonian cycles and edge-colourings in a class of cubic graphs
%J Ars Mathematica Contemporanea
%D 2023
%V 23
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2672.73b/
%R 10.26493/1855-3974.2672.73b
%G en
%F 10_26493_1855_3974_2672_73b
Marién Abreu; John Baptist Gauci; Domenico Labbate; Federico Romaniello; Jean Paul Zerafa. Perfect matchings, Hamiltonian cycles and edge-colourings in a class of cubic graphs. Ars Mathematica Contemporanea, Tome 23 (2023) no. 3, article  no. 01, 18 p. doi : 10.26493/1855-3974.2672.73b. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2672.73b/

Cité par Sources :