Seminar of Graph Theory - István Porupsánszki (21.3.2024)
Thursday 21.3.2024 at 9:50 hod., Lecture room C
István Porupsánszki (Eotvos Lorand University, Budapest):
New families of (almost) edge-girth-regular graphs
Abstract:
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.