Faculty of Mathematics, Physics
and Informatics
Comenius University in Bratislava

Seminar of Graph Theory - Jozef Rajník (6.5.2021)

Thursday 6.5.2021 at 9:50


04. 05. 2021 14.58 hod.
By: Martin Škoviera

Jozef Rajník:
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)

Abstract:
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á. 


More information