Seminár z teórie grafov - Martin Škoviera (20.10.2022)

vo štvrtok 20.10.2022 o 9:50 hod. v miestnosti M/213

18. 10. 2022 11.44 hod.
Od: Martin Škoviera

Prednášajúci: Martin Škoviera

Názov: Decycling cubic graphs

Termín: 20.10.2022, 9:50 hod., M 213

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.

Stránka seminára