Faculty of Mathematics, Physics
and Informatics
Comenius University Bratislava

Algebraic Graph Theory Seminar - Jozef Rajník (5.4.2024)

Friday 5.4.2024 at 13:00, Lecture room M/IX (online too)

02. 04. 2024 20.48 hod.
By: Martin Mačaj

Jozef Rajník:
Algebraic constructions related to cyclic connectivity

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.