Seminar of Graph Theory - Pavol Jánoš (28.4.2022)

Thursday 28.4.2022 at 9:50, Lecture room M/213

26. 04. 2022 10.03 hod.
By: Martin Škoviera

Pavol Jánoš (STU Bratislava):
On near-cages from lifts of dipoles

Abstrakt:
The problem of finding $(k,g)$-cages, that is, finding the smallest (in terms of the number of vertices) $k$-regular graphs of girth $g$ is largely open. One of the approaches of finding small graphs with given properties are lifting constructions. In this talk we examine our constructions of small $k$-regular graphs of girth 6 and 8, obtained by lifting dipoles and achieving the order of existing graphs of the corresponding girth. We also discuss another construction based on groups, called $G$-graphs, and show under which circumstances the $G$-graphs can be obtained as lifts of dipoles.

This work is joint with Š. Gyürki, J. Šiagiová and J. Širáň

More information