Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903567 | European Journal of Combinatorics | 2018 | 13 Pages |
Abstract
We consider a new type of regularity we call edge-girth-regularity. An edge-girth-regular (v,k,g,λ)-graph Πis a k-regular graph of order v
and girth g in which every edge is contained in λ distinct g-cycles. This concept is a generalization of the well-known concept of (v,k,λ)-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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Robert Jajcay, György Kiss, Å tefko MiklaviÄ,