Atlantic Graph Theory Seminar: Jorik Jooken – Feb 4

Speaker: Jorik Jooken, KU Leuven Kulak

Title: On vertex-girth-regular graphs: (Non-)existence, bounds and enumeration

Abstract: A vertex-girth-regular vgr(v,k,g,lambda)-graph is a k-regular graph of girth g and order v in which every vertex belongs to exactly lambda cycles of length g. While all vertex-transitive graphs are necessarily vertex-girth-regular, the majority of vertex-girth-regular graphs are not vertex-transitive. Similarly, while many of the smallest k-regular graphs of girth g, the so-called (k,g)-cages, are vertex-girth-regular, infinitely many vertex-girth-regular graphs of degree k and girth g exist for many pairs k, g. Due to these connections, the study of vertex-girth-regular graphs promises insights into the relations between the classes of extremal, highly symmetric, and locally regular graphs of given degree and girth. This paper lays the foundation to such study by investigating the fundamental properties of vgr(v,k,g,lambda)-graphs, specifically the relations necessarily satisfied by the parameters  and to admit the existence of a corresponding vertex-girth-regular graph, by presenting constructions of infinite families of vgr(v,k,g,lambda)-graphs, and by establishing lower bounds on the number v of vertices in a vgr(v,k,g,lambda)-graph. It also includes computational results determining the orders of smallest cubic and quartic graphs of small girths.

Full paper: https://www.combinatorics.org/ojs/index.php/eljc/article/view/v32i4p51

Zoom link:

Meeting ID: 880 1326 1876