Seminár z teórie grafov - Jozef Rajník (6.5.2021)
vo štvrtok 6.5.2021 o 9:50 hod. online formou
Od: Martin Škoviera
Prednášajúci: Jozef Rajník
Názov: Decomposition of cubic graphs with cyclic connectivity
Termín: 6.5.2021, 9:50 hod.
Prístupový kód do MS TEAMS (pre používateľov z UK): gglxxc7
Pripojenie (pre hostí mimo UK)
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á.