Sulle ineccepibili relazioni tra i matching perfetti

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.

Snarks e Hamiltonicità sono due rilevanti aree di ricerca nella Teoria dei Grafi. Come suggerisce il titolo, in questa tesi studieremo come interagiscono tra loro i matching perfetti di un grafo, in particolare ci occuperemo di studiare la loro unione e intersezione nei due ambiti sopra indicati. Gli snarks, grafi cubici privi di ponti e di Classe II, sono oggetti cruciali quando si considerano congetture su grafi cubici senza ponti, perchè, tipicamente, se una congettura viene verificata per gli snarks allora è valida in generale. Una di queste congetture, nota per il suo enunciato particolarmente semplice ma completamente aperta dopo oltre mezzo secolo, è la Congettura di Berge–Fulkerson. Nella prima parte di questa tesi studieremo altre due ben note congetture entrambe conseguenze della congettura di Berge–Fulkerson e che sono anche esse ancora aperte: la Congettura di Fan–Raspaud (Fan & Raspaud 1994) e la Congettura S4 (Mazzuoccolo 2013). La prima riguarda il comportamento dell’intersezione di tre matching perfetti e l’altra il complemento dell’unione di due matching perfetti. Diamo una formulazione equivalente della Congettura di Fan–Raspaud che in letteratura appariva essere una versione più forte, e mostriamo che la Congettura S4 è vera per grafi cubici senza ponti di oddness al più 4. A causa degli ostacoli che si incontrano nello studiare tali tipi di problemi, sono stati fatti molti tentativi di colmare il gap tra grafi cubici di Classe I e di Classe II introducendo invarianti che misurino quanto un grafo di Classe II è lontano dall’essere di Classe I. In questo spirito, proponiamo di considerare il minimo numero di matching perfetti (non necessariamente distinti) che è necessario aggiungere a un grafo cubico senza ponti per ottenere un multigrafo di Classe I. Dimostriamo che il grafo di Petersen è sostanzialmente l’unica ostruzione per questo problema, nel senso che non ammette un numero finito di matching perfetti con la proprietà richiesta. Inoltre, colleghiamo lo studio di questo problema ad altri ben noti: l’excessive index e la lunghezza della più corta copertura in cicli. Nella seconda parte della tesi, studiamo un problema legato all’Hamiltonicità di un grafo, già introdotto negli anni settanta da Las Vergnas e Häggkvist, e poi generalizzato più di recente da Fink (2007). Ci riferiamo a grafo Hamiltoniani con un numero pari di vertici (condizione necessaria per avere un matching perfetto): in tali grafi, un ciclo Hamiltoniano lo si può vedere come unione di due matching perfetti. Diremo che G ha la Perfect-Matching-Hamiltonian property (in breve la PMH-property) se ogni suo matching perfetto si può estendere a un ciclo Hamiltoniano. Una proprietà ancora più forte è la seguente: un grafo G ha la Pairing-Hamiltonian property (in breve la PH-property) se ogni pairing di G (cioè un matching perfetto del grafo completo definito sugli stessi vertici di G) può essere esteso a un ciclo Hamiltoniano del grafo completo soggiacente usando un matching perfetto di G. Una caratterizzazione dei grafi cubici con la PH-property è stata fornita da Alahmadi e al. (2015). Gli stessi autori hanno solo parazialmente tentato una caratterizzazione anche dei grafi 4-regolari con la stessa proprietà. Noi risolviamo uno dei problemi da loro proposti e mostriamo una famiglia di grafi 4-regolari, che chiameremo accordion, che riteniamo interessante in quest’ambito. Le proprietà di Hamiltonicità sono state ampiamente studiate anche per i line-graphs da, tra gli altri, Kotzig (1964), Harary & Nash-Williams (1965) e Thomassen (1986). In questa linea di ricerca diamo condizioni sufficienti per un grafo che garantiscano la PMH-property per il suo line-graph. Otteniamo tali risultati per grafi di grado al più 3, grafi completi e grafi arbitrarily traceable. Infine otteniamo una caratterizzazione completa dei line graphs dei grafi bipartiti completi che ammettono la PH-property.