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

05. 10. 2020 19.32 hod.
Od: Martin Škoviera

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.