Faculty of Mathematics, Physics
and Informatics
Comenius University in Bratislava

Seminar of Graph Theory - Róbert Jajcay (1.10.2020)

Thursday 1.10.2020 at 9:50, Lecture room M/213


29. 09. 2020 22.42 hod.
By: Martin Škoviera

Róbert Jajcay:
Extremal edge-girth-regular graphs


Abstract:
The aim of the talk is to generalize properties satisfied by highly symmetric (vertex-, edge- or arc-transitive) graphs to larger classes of graphs and to look for families of graphs that share some of the properties of symmetric graphs but are not themselves symmetric.

One such class is the class of edge-girth-regular $egr(v,k,g,\lambda)$-graphs which are $k$-regular graphs of order $v$ and girth $g$ in which every edge is contained in $\lambda$ distinct $g$-cycles. Beside the obvious edge-transitive graphs, examples include other important classes of graphs such as Moore graphs, as well as many of extremal $k$-regular graphs of prescribed girth or diameter. Infinitely many $egr(v,k,g,\lambda)$-graphs are known to exist for sufficiently large parameters $(k,g,\lambda)$, 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,\lambda)$.

We derive lower bounds in terms of the parameters $k,g$ and $\lambda$. We also determine the orders of the smallest $egr(v,k,g,\lambda)$-graphs for some specific parameters $(k,g,\lambda)$, and address the problem of the smallest possible orders of bipartite edge-girth-regular graphs.

Joint work with A. Zavrtanik Drglin, S. Filipovski, and T. Raiman.