Edge-girth-regular graphs

Robert Jajcay (Avtor), György Kiss (Avtor), Štefko Miklavič (Avtor)

Povzetek

We consider a new type of regularity we call edge-girth-regularity. An edge-girth-regular ▫$(v, k, g, \lambda)$▫-graph ▫$\varGamma$▫ 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 concept of ▫$(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.

Ključne besede

girth;edge-regular graph;edge-girth-regular graph;regular embeddings of graphs in orientable surfaces;Moore graphs;

Podatki

Jezik:	Angleški jezik
Leto izida:	2018
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UP - Univerza na Primorskem
UDK:	519.17
COBISS:	1540315332
ISSN:	0195-6698
Št. ogledov:	1972
Št. prenosov:	370
Ocena:	0 (0 glasov)
Metapodatki: