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

Thursday 8.10.2020 at 9:50, Lecture room M/213

05. 10. 2020 19.36 hod.
By: Martin Škoviera

Jozef Rajník:
Decomposition of cyclically 4-connected cubic graphs

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