You are here: Home » Research » Publications Details

Publications of the Department


Zerafa, JEAN PAUL, (2021)  - Sulle ineccepibili relazioni tra i matching perfetti  - , Tesi di dottorato - (, , Universitą degli studi di Modena e Reggio Emilia ) - pagg. -

Abstract: Snarks and Hamiltonicity: two prominent areas of research in graph theory. As the title of the thesis suggests, here we study how perfect matchings behave together, more precisely, their union and intersection, in each of these two settings. Snarks, which for us represent Class II bridgeless cubic graphs, are crucial when considering conjectures about bridgeless cubic graphs, and, if such statements are true for snarks then they would be true for all bridgeless cubic graphs. One such conjecture which is known for its simple statement, but still indomitable after half a century, is the Berge–Fulkerson Conjecture. In the first part of the thesis we study two other related and well-known conjectures about bridgeless cubic graphs, both consequences of the Berge–Fulkerson Conjecture which are still very much open: the Fan–Raspaud Conjecture (Fan & Raspaud, 1994) and the S4-Conjecture (Mazzuoccolo, 2013), dealing with the intersection of three perfect matchings, and the complement of the union of two perfect matchings, respectively. In particular, we give an equivalent formulation of the Fan–Raspaud Conjecture which at first glance seems stronger, and show that the S4-Conjecture is true for bridgeless cubic graphs having oddness at most 4. Given the obstacles encountered when dealing with such problems, many have considered trying to bridge the gap between Class I and Class II bridgeless cubic graphs by looking at invariants that measure how far Class II bridgeless cubic graphs are from being Class I. In this spirit we consider a parameter which gives the least number of perfect matchings (not necessarily distinct) needed to be added to a bridgeless cubic graph such that the resulting multigraph is Class I. We show that the Petersen graph is, in some sense, the only obstruction for a bridgeless cubic graph to have a finite value for the parameter studied. We also relate this parameter to already well-studied concepts: the excessive index, and the length of a shortest cycle cover of a bridgeless cubic graph. In the second part, we study a concept about Hamiltonicity first considered in the 1970s by Las Vergnas and Häggkvist, which was generalised and recently brought to the limelight again by Fink (2007). In this part we look at Hamiltonian cycles in graphs having an even order (a necessary condition for a graph to admit a perfect matching). In such graphs, a Hamiltonian cycle can be seen as the union of two perfect matchings. If every perfect matching of a graph G extends to a Hamiltonian cycle, we say that G has the Perfect-Matching-Hamiltonian property (for short the PMH-property). A stronger property than the PMH-property is the following: a graph G has the Pairing-Hamiltonian property (for short the PH-property) if every pairing of G (i.e. a perfect matching of the complete graph having the same vertex set as G) can be extended to a Hamiltonian cycle of the underlying complete graph by using a perfect matching of G. A characterisation of all the cubic graphs having the PH-property was done by Alahmadi et al. (2015), and the same authors attempt to answer a most natural question, that of characterising all 4-regular graphs having the same property. We solve a problem they suggest regarding quartic graphs and the above properties, and propose a class of quartic graphs on two parameters, accordion graphs, which we believe is a rich one in this sense. Hamiltonicity was also heavily studied with respect to line graphs by Kotzig (1964), Harary & Nash-Williams (1965), and Thomassen (1986), amongst others, and along the same lines, we give sufficient conditions for a graph in order to guarantee the PMH-property in its line graph. We do this for subcubic graphs, complete graphs, and arbitrary traceable graphs. A complete characterisation of which line graphs of complete bipartite graphs admit the PH-property is given.