Discrete mathematics seminar: Extremal edge-girth-regular graphs

Dates

Wednesday, March 3, 2021 - 14:00 to 15:00

Speaker: Robert Jajcay (Comenius University, Bratislava)

Title: Extremal edge-girth-regular graphs

Abstract:

Edge-girth-regular graphs retain the local symmetry properties of highly symmetric (edge-transitive) graphs without necessarily admitting a large group of automorphisms. Moreover, many of the extremal graphs with prescribed degree and girth (the so-called cages) or graphs with prescribed degree and diameter belong to the class of edge-girth-regular graphs, and thus, edge-girth-regular graphs constitute a bridge between Algebraic and Extremal Graph Theory.

An edge-girth-regular egr(v,k,g,λ)-graph is a k-regular graph of order v and girth g in which every edge is contained in λ distinct g-cycles. Infinitely many egr(v,k,g,λ)-graphs are known to exist for sufficiently large parameters (k,g,λ), and in line with the well-known Cage Problem we attempt to determine the smallest graphs among all edge-girth-regular graphs for given parameters (k,g,λ).

To achieve this, we derive lower bounds in terms of the parameters k, g and λ. We also determine the orders of the smallest egr(v,k,g,λ)-graphs for some specific parameter triples (k,g,λ), and address the problem of the smallest possible orders of bipartite edge-girth-regular graphs.

Presented results come from joint work with A. Zavrtanik Drglin, S. Filipovski, and T. Raiman.