Girth-regular graphs - Potočnik, Primož (Ars mathematica contemporanea, 2019)
We introduce a notion of a girth-regular graph as a ?$k$?-regular graph for which there exists a non-descending sequence ?$(a_1, a_2, … , a_k)$? (called the signature) giving, for every vertex ?$u$? of the graph, the number of girth cycles the edges with end-vertex ?$u$? lie on. Girth-regularity generalises two very different aspects of symmetry in graph theory: that of vertex transitivity and that of distance-regularity. For general girth-regular graphs, we give some results on the extremal cases of signatures. We then focus on the cubic case and provide a characterisation of cubic girth-regular graphs of girth up to 5.
Keywords: cubic; girth; girth-regular; graf; graph; kubični grafi; ožina; ožinska regularnost