Seminár z teórie grafov - Jozef Rajník (10.11.2022)
vo štvrtok 10.11.2022 o 9:50 hod. v miestnosti M/213
Od: Martin Škoviera
Prednášajúci: Jozef Rajník
Názov: Cyclic connectivity of cubic cages
Termín: 10.11.2022, 9:50 hod., M 213
The famous cage problem asks for finding a smallest k-regular graph with girth g (that is, the length of a shortest cycle) also called a (k,g)-cage. As our main result, we prove that every (3,13)-cage is cyclically 13-edge-connected, that is, it contains no set of fewer than 13 edges that separates two cycles. Note that all 3-regular cages are known up to girth 12 and each of them has its cyclic edge-connectivity equal to its girth. The girth 13 is thus the smallest girth for which the exact order of a cage is not known (it lies between 202 and 272).
Our main idea consists of extending the cubic case of the cage problem to subcubic graphs: we ask for a smallest graph with a finite girth at least g, exactly l vertices of degree 2 and all the remaining vertices of degree 3. We develop techniques for approaching this problem and present our results in small cases. Also, we will discuss possible generalisations of our results and relation to the problem whether each cycle separating g-edge-cut in a (3, g)-cage separates a cycle. We believe our results will shed some new light on the cage problem and perhaps lead to some improvements in exhaustive computer searches. This is a joint work with Edita Máčajová.