Seminár z teórie grafov - Martin Škoviera (20.10.2022)
vo štvrtok 20.10.2022 o 9:50 hod. v miestnosti M/213
Prednášajúci: Martin Škoviera
Názov: Decycling cubic graphs
Termín: 20.10.2022, 9:50 hod., M 213
Abstrakt:
Destroying all cycles of a graph by removing as few vertices as possible is an extensively studied problem in graph theory and computer science. The minimum number of vertices whose deletion eliminates all cycles of a graph is its decycling number. In this talk we deal with the problem of determining the decycling number of a cubic graph. We show that the problem is closely related to determining the largest genus of an orientable surface into which the graph can be cellularly embedded. Using this relationship we prove that every cyclically 4-connected cubic graph G has a minimum decycling set S such that G-S is connected (that is, a tree) and S itself is either independent or induces a subgraph with exactly one edge. This improves a classical result of Payan and Sakarovitch (1975).
We conjecture that such a decycling set exist in almost all cubic graphs.
This is a joint work with Roman Nedela and Michaela Seifrtova.