Seminár z teórie grafov - Jozef Rajník (9.12.2021)
vo štvrtok 9.12.2021 o 9:50 hod. online formou
Od: Martin Škoviera
Prednášajúci: Jozef Rajník
Názov: Decomposition of cubic graphs with cyclic connectivity 6 and beyond
Termín: 16.12.2021, 9:50 hod., MS Teams
Pristupový kód do MS TEAMS je: gglxxc7
(pre účastníkov z UK v Bratislave)
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á.