Faculty of Mathematics, Physics
and Informatics
Comenius University Bratislava

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

Thursday 9.12.2021 at 9:50, online

06. 12. 2021 14.25 hod.
By: Martin Škoviera

Jozef Rajník:
Decomposition of cubic graphs with cyclic connectivity 6 and beyond

MS Teams 

Access code for MS TEAMS je: gglxxc7
(Access code for Comenius University only)

In this talk we examine the following question. Let G be a cyclically k-edge-connected cubic graph with a k-edge-cut separating a cyclic component C different from the k-cycle. How can we complete C to a cyclically k-edge-connected cubic graph H? Our work extends the results of Andersen et al. from 1988 who studied this problem for the case k = 4, and our recent results for the case k = 5. We show that if the resulting graph H has girth at least k and H – C is cyclic and different from the k-cycle, then H is cyclically k-edge-connected. Based on this result we provide an algorithm determining whether a given graph C can be a subgraph of some cyclically k-edge-connected cubic graph. Moreover, for k = 6 we show that each such component C can be completed to a cyclically 6-edge-connected cubic graph by adding 8 additional vertices forming two 6-cycles that share a path of length three.

This is a joint work with Edita Máčajová.

More information