On the consummate affairs of perfect matchings

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 which states that every bridgeless cubic graph G admits six perfect matchings such that every edge in G is contained in exactly two of these six perfect matchings. In this 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 and 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. 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. We also show that the S4-Conjecture can be stated in terms of a variant of Petersen-colourings, and discuss it in relation to bridgeless cubic multigraphs and certain cubic multigraphs having bridges. 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. This is done in an attempt to further refine the class of snarks, and thus, enlarging the set of cubic graphs for which such conjectures can be verified. 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 particular, we show that an infinite family of non-trivial snarks, a generalisation of treelike snarks, have a shortest cycle cover with length strictly greater than 4/3 their size. This is done in the first part of the thesis. 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 circuits in graphs having an even order, which is a necessary condition for a graph to admit a perfect matching. In such graphs, a Hamiltonian circuit can be seen as the union of two perfect matchings. If every perfect matching of a graph G extends to a Hamiltonian circuit, we say that G has the Perfect-Matching-Hamiltonian property (for short the PMH-property). A somewhat stronger property than the PMH-property is the following: a graph G has the Pairing-Hamiltonian property if every pairing of G (that is, a perfect matching of the complete graph having the same vertex set as G) can be extended to a Hamiltonian circuit of the underlying complete graph using only edges from G, that is, 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. They do this by posing the following problem: for which values of p and q does the Cartesian product Cp Cq of two circuits on p and q vertices have the PH-property? We show that this only happens when both p and q are equal to four, namely for C4 C4, the 4-dimensional hypercube. We continue this study of quartic graphs in relation to the above properties by proposing a class of quartic graphs on two parameters, accordion graphs, a class which we believe is a rich one in this sense. A complete characterisation of which accordion graphs are circulant is also given. Hamiltonicity was also heavily studied with respect to line graphs by Kotzig (1964), Harary and 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. Moreover, we also give a complete characterisation of which line graphs of complete bipartite graphs admit, not only the PMH-property, but the PH-property.