Janoš Vidali: Cubic girth-regular graphs of small girth
Source: Discrete mathematics seminar
Povzetek. Let Γ be a k-regular graph of girth g. Suppose there exist integers s1 ≤ s2 ≤ ... ≤ sk such that for each vertex u of Γ, the k arcs with initial vertex u lie on s1, s2, ... sk girth cycles. Such a graph is said to be girth-regular with signature (s1, s2, ... sk). Girth-regular graphs include many classes of graphs, such as vertex-transitive, semi-symmetric and distance-regular graphs, as well as skeletons of many uniform maps and their truncations.We focus on cubic girth-regular graphs, for which we derive some conditions on their signatures (a, b, c). We then obtain classifications for girth-regular graphs with small and large values of c, and for girth-regular graphs of girth at most 6. We also check for signatures appearing among vertex-transitive graphs of larger girths on at most 1280 vertices from the census by Potočnik, Spiga and Verret.