Faculty of Mathematics, Physics
and Informatics
Comenius University Bratislava

Seminar of Graph Theory - István Porupsánszki (21.3.2024)

Thursday 21.3.2024 at 9:50 hod., Lecture room C

19. 03. 2024 09.31 hod.
By: Martin Škoviera

István Porupsánszki (Eotvos Lorand University, Budapest):
New families of (almost) edge-girth-regular graphs

The famous cage problem consists in finding k-regular graphs of girth g with minimal order. We know some lower bounds (Moore-bound) but in general this is a barely solved problem.
In my talk, I will introduce an alternative problem. An egr graph is a k-regular graph of girth g such that every edge is contained in exactly ? distinct girth cycles. With the incidence graph some finite geometrical structures we can construct egr graphs. However, since the initial graphs are bipartite we obtain egr graphs of even girth. At the end of my talk, I will talk about some techniques to obtain new families of (almost) egr graphs of girth 5.

More information