Fakulta matematiky, fyziky
a informatiky
Univerzita Komenského v Bratislave

Seminár z algebraickej teórie grafov - Jozef Rajník (5.4.2024)

v piatok 5.4.2024 o 13:00 hod. v posluchárni M IX aj online

02. 04. 2024 20.11 hod.
Od: Martin Mačaj

Prednášajúci: Jozef Rajník

Názov: Algebraic constructions related to cyclic connectivity

Termín: 5.4.2024, 13:00 hod., M IX a MS Teams 

Consider a cubic graph G and a k-edge cut S such that G - S has two components G1 and G2, each containing a cycle, and k is the smallest possible. The value of k is called the cyclic (edge-) connectivity of G and each of G1 and G2 is called a cyclic k-part which we regard as a 3-regular "graph" with k semiedges, formally called a k-pole. In many situations, it is useful to complete each Gi to a cyclically k-connected cubic graph by joining Gi with some suitable k-pole. A k-pole U is called a universal k-adjunct if, for any cyclic k-part M, each possible junction of U and M yields a cyclically k-connected cubic graph. In this talk, we present a lower bound on the order of a universal k-adjunct and various lift constructions that meet this lower bound for even k <= 14. We discuss possibilities for improvements and connections to the cage problem.

Those of you who are not able to attend in person or who are still uncertain about the safety of attending in person are welcome to attend via MS Teams. In either case, we hope to see as many of you as possible (either in person or virtually) at our Friday gatherings.