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

08. 11. 2022 09.24 hod.
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á.


Stránka seminára