• ciclo
• grafo cubico
• grafo regolare
• k-fattore
• matching perfetto

La trattazione si colloca all'interno del filone di ricerca nato a partire dalla formulazione della Congettura di Berge-Fulkerson negli anni settanta e in particolare affronta la seguente versione più debole di tale congettura: ogni grafo cubico e privo di ponti due matching perfetti la cui rimozione lascia un grafo bipartito. All'interno della tesi viene presentata e discussa nel dettaglio una recente dimostrazione di tale risultato proposta da Kardoš, Máčajová e Zerafa. A tal fine vengono riportati diversi risultati inerenti alla connettività ciclica sugli spigoli dei grafi cubici. La seconda parte della trattazione è dedicata alla presentazione di alcuni risultati originali che generalizzano il precedente teorema. In particolare viene dimostrato che dato un qualunque grafo 4-regolare e 2-connesso è possibile determinare un 2-fattore che intersechi ogni ciclo di una famiglia assegnata in almeno uno spigolo. L’interesse per tale risultato deriva dal fatto che l’analogo problema per i grafi cubici è un’immediata conseguenza del teorema di Kardoš, Máčajová e Zerafa precedentemente menzionato. Il secondo risultato che si cerca di generalizzare è un altro corollario del medesimo teorema, il quale afferma che in un grafo cubico e privo di ponti il massimo numero di matching perfetti che è necessario rimuovere per ottenere un grafo bipartito è 2. A tal proposito viene costruita una famiglia di r-grafi con lo scopo di determinare una stima dal basso a tale numero in funzione della regolarità del grafo. La trattazione si conclude presentando alcune congetture e problemi aperti relativi agli argomenti trattati.

This dissertation fits into the framework of the stream of research that began in the 1970s with the formulation of the Berge-Fulkerson Conjecture and focuses on the following weaker version of the conjecture: every bridgeless cubic graph admits two perfect matchings whose deletion yields a bipartite graph. In this thesis, we present and study the details of a recent proof of this result by Kardoš, Máčajová and Zerafa. To this end, various results on cyclic edge connectivity of cubic graphs are presented. The second part of the dissertation presents some original results generalising the previous theorem. More precisely, it is shown that for a 4-regular and 2-connected graph it is possible to determine a 2-factor that intersects every cycle of a given family in at least one edge. The interest in this result is due to the fact that the corresponding problem for cubic graphs is a direct consequence of the theorem of Kardoš, Máčajová and Zerafa mentioned earlier. The second result which we try to generalise is another corollary of the same theorem. The corollary states that the maximum number of perfect matchings to be removed in a bridgeless cubic graph to obtain a bipartite graph is 2. For this purpose, a family of r-graphs is built to determine a lower bound for this number based on the regularity of the graph. This thesis ends with the presentation of some conjectures and unsolved problems related to these topics.