Seminar of Theoretical Computer Science - Jorik Jooken (15.3.2024)

Friday 15.3.2024 at 11:00, Lecture room F 108

11. 03. 2024 20.04 hod.
By: Rastislav Královič

Jorik Jooken (Katholieke Universiteit, Leuven):
Computational bounds for the minimum order of an edge-girth-regular graph

Abstract:
An edge-girth-regular(v,k,g,lambda) graph is a k-regular graph of order v and girth g such that each edge is contained in precisely lambda girth cycles. These graphs generalize several well known classes of graphs such as edge-regular graphs, edge-transitive graphs and arc-transitive graphs. In this seminar, we discuss an algorithm to exhaustively generate all edge-girth-regular graphs of a fixed order and improve several bounds on the minimum order of these graphs for certain tuples (k,g,lambda). In this seminar, we will also discuss implementation aspects that are not described in the paper. Full paper: https://arxiv.org/pdf/2401.08271.pdf