Seminár z teórie grafov - Jozef Rajník (7.3.2024)
vo štvrtok 7.3.2024 o 9:50 hod. v posluchárni C
Prednášajúci: Jozef Rajník
Názov: Cyclic Connectivity and Cages - Considering Connections
Termín: 7.3.2024, 9:50 hod., poslucháreň C
Abstrakt:
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á.