On edge-girth-regular graphs

We consider a new type of regularity we call edge-girth-regularity. An edge-girth-regular ((v,k,g,lambda))-graph (G) is a (k)-regular graph of order (v) and girth (g) in which every edge is contained in (lambda) distinct (g)-cycles. This concept is a generalization of the well-known ((v,k,lambda))-edge-regular graphs (that count the number of triangles) and appears in several related problems such as Moore graphs and Cage and Degree/Diameter Problems. All edge- and arc-transitive graphs are edge-girth-regular as well. We derive a number of basic properties of edge-girth-regular graphs, systematically consider cubic and tetravalent graphs from this class, and introduce several constructions that produce infinite families of edge-girth-regular graphs. We also exhibit several surprising connections to regular embeddings of graphs in orientable surfaces.

Joint work with Robert Jajcay and Štefko Miklavič.