Seminár z teórie grafov - Jozef Rajník (8.10.2020)
vo štvrtok 8.10.2020 o 9:50 hod. v miestnosti M/213
Prednášajúci: Jozef Rajník
Názov: Decomposition of cyclically 4-connected cubic graphs
Termín: 8.10.2020, 9:50 hod., M/213
Abstrakt:
Let $G$ be a cyclically $4$-connected cubic graph with a cycle separating $4$-edge-cut $S$ and let $H$ be one component of $G - S$. We give the necessary and sufficient condition under which the component $H$ can be extended to a cyclically $4$-connected cubic graph of the same order by adding two edges. Our work completes the result of Goedgebeur, Máčajová and Škoviera, who showed that the component $H$ can be extended to a cyclically $4$-connected cubic graph by adding two adjacent vertices and restoring $3$-regularity. These results provide useful induction methods for cyclically $4$-connected cubic graphs.
This is a joint work with Edita Máčajová. The same results were also published by Andersen, Fleischner and Jackson.