Seminar of Graph Theory - Jozef Rajník (9.12.2021)
Thursday 9.12.2021 at 9:50, online
Jozef Rajník:
Decomposition of cubic graphs with cyclic connectivity 6 and beyond
Access code for MS TEAMS je: gglxxc7
(Access code for Comenius University only)
Abstract:
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á.