Seminar of Graph Theory - Jozef Rajník (6.5.2021)
Thursday 6.5.2021 at 9:50
By: Martin Škoviera
Decomposition of cubic graphs with cyclic connectivity
Termín: 6.5.2021, 9:50 hod.
MS TEAMS code (users from Comenius University in Bratislava): gglxxc7
Link (guests outside Comenius University in Bratislava)
Let G be a cyclically 5-connected cubic graph with a 5-edge-cut separating G into two cyclic components G_1 and G_2. We prove that each component G_i can be completed to a cyclically 5-connected cubic graph by adding three vertices, unless G_i is a cycle of length five. Our work extends similar results by Andersen et al. for cyclic connectivity 4 from 1998.
Our results enable us to use inductive arguments in the class of the cubic graphs with cyclic connectivity 5. Also, this inductive approach can be used in computer-assisted constructions of cubic graphs with cyclic connectivity 5 and other prescribed properties such as large girth or oddness. This is a joint work with Edita Máčajová.