On edge-girth-regular graphs: lower bounds and new families

Abstract

An edge-girth-regular graph $egr(n,k,g,\lambda )$ is a $k-$regular graph of order $n$, girth $g$ and with the property that each of its edges is contained in exactly $\lambda$ distinct $g-$cycles. We present new families of edge-girth regular graphs arising from generalized quadrangles and pencils of elliptic quadrics. An $egr(n,k,g,\lambda )$ is called extremal for the triple $(k,g,\lambda )$ if $n$ is the smallest order of any $egr(n,k,g,\lambda )$. We give new lower bounds for the order of extremal edge-girth-regular graphs using properties of the eigenvalues of the adjacency matrix of a graph.

13 pages, 2 figures