Seminar of Graph Theory - Róbert Jajcay (19.3.2026)
Thursday 19.3.2026 at 9:50, Lecture room M 213
Róbert Jajcay:
Bounded Diameter/Girth Ratio Problem in the center of Extremal Graph Theory
Abstract:
The main problem we address in our presentation relates three graph parameters often considered in Extremal Graph Theory: k, the degree of a k-regular graph; D, the diameter of a graph; and g, the girth. Unlike many of the problems in Extremal Graph Theory, our problem, which we shall call the "Bounded Diameter/Girth Ratio Problem", is not about maximizing or minimizing any other related parameter, but it is about finding infinite families of k-regular graphs of fixed degree k >= 3 whose diameters and girths are tied together: For a given k >= 3, construct an infinite family Gamma_i of k-regular graphs of girths g_i and diameters D_i for which there exists a positive constant c bounding the diameter/girth ratios of these graphs from above, D_i/g_i =< c , for all i >= 1.
The presented results stem from joint work with Gabriela Araujo-Pardo and Stefania Glevitzka.