Seminar of Graph Theory - Jozef Rajník (7.3.2024)
Thursday 7.3.2024 at 9:50 hod., Lecture room C
Jozef Rajník:
Cyclic Connectivity and Cages - Considering Connections
Abstract:
In this talk, we shall discuss connections between these two research topics, which have been widely studied but mostly separately. The cyclic edge-connectivity of a graph G is the smallest cardinality of an edge-cut that separates two cycles in G. It proved to be an important invariant of mostly cubic graphs and it emerges in various proofs and the study of smallest counter-examples. On the other hand, a (k,g)-cage is a smallest k-regular graph with girth g. We will show how cages and similar structures emerge in decomposing two cubic graphs with cyclic edge-connectivity k into two smaller cyclically k-connected cubic graphs. Moreover, we propose a conjecture that all (k, g)-cages are cyclically (k-2)g-edge connected, which is the larges possible value of cyclic connectivity. We prove this conjecture for (k,g)-cages with order at most roughly twice the Moore bound. This implies that the conjecture holds for some small pairs of (k,g) for which the order of a cage is not known including the famous hypothetical Moore graph of degree 57 and girth 5.
This is a joint work with Robert Lukoťka and Edita Máčajová.