Seminár z teórie grafov - Matúš Matok (21.5.2026)
vo štvrtok 21.5.2026 o 9:50 hod. v miestnosti M 213
Prednášajúci: Matúš Matok
Názov prednášky: Lonely edges in cubic graphs
Termín: 21.5.2026, 9:50 hod., M 213
Abstrakt:
The notion of a perfect matching, i.e., a 1-regular spanning subgraph—a set of disjoint edges covering all vertices of a given graph—is a well studied subject in graph theory. Already in 1891, Petersen proved that each edge of a bridgeless cubic graph can be covered by a perfect matching. We say that an edge e is matching double covered if there exist two distinct perfect matchings containing e. Otherwise, e is said to be lonely. If all edges of a graph are matching double covered, so is the graph. A graph G is Klee if it is the complete graph on 4 vertices or it is obtained from another Klee graph by the operation of replacing a vertex with a triangle. This operation is denoted as G ↑ v for some vertex v ∈ V(G) of G. All Klee graphs are therefore 3-connected and planar. The classes of Klee graphs with more than three lonely edges have been characterized by Goedgebeur [1] et al.
Wedefineanauxiliary structure called a decomposition tree which is a well-defined object with respect to a lonely edge e ∈ E(G) of a graph G. With the help of decomposition trees, we can argue about loneliness of e in G ↑ v for all vertices of G, giving us both positive and negative certificates of this status. This allows us to characterize all graphs with one or two lonely edges, hence completing the characterization of cubic graphs with lonely edges.
References:
[1] Jan Goedgebeur and Davide Mattiolo and Giuseppe Mazzuoccolo and Jarne Renders and Isaak H. Wolf : Cubic graphs with edges in exactly one perfect https://arxiv.org/abs/2402.08538