On extremal (almost) edge-girth-regular graphs

Abstract

A $k$-regular graph of girth $g$ is called edge-girth-regular graph, shortly egr-graph, if each of its edges is contained in exactly $\lambda$ distinct $g-$cycles. An egr-graph is called extremal for the triple $(k,g,\lambda )$ if has the smallest possible order. We prove that some graphs arising from incidence graphs of finite planes are extremal egr-graphs. We also prove new lower bounds on the order of egr-graphs.

24 pages, 5 figures