Extremal Edge-Girth-Regular Graphs
| Autor: | Tom Raiman, Ajda Zavrtanik Drglin, Robert Jajcay, Slobodan Filipovski |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Zdroj: | Graphs and Combinatorics. 37:2139-2154 |
| ISSN: | 1435-5914 0911-0119 |
| Popis: | An edge-girth-regular $$egr(v,k,g,\lambda )$$ -graph $$\Gamma $$ is a k-regular graph of order v and girth g in which every edge is contained in $$\lambda $$ distinct g-cycles. Edge-girth-regularity is shared by several interesting classes of graphs which include edge- and arc-transitive graphs, Moore graphs, as well as many of the extremal k-regular graphs of prescribed girth or diameter. Infinitely many $$egr(v,k,g,\lambda )$$ -graphs are known to exist for sufficiently large parameters $$(k,g,\lambda )$$ , and in line with the well-known Cage Problem we attempt to determine the smallest graphs among all edge-girth-regular graphs for given parameters $$(k,g,\lambda )$$ . To facilitate the search for $$egr(v,k,g,\lambda )$$ -graphs of the smallest possible orders, we derive lower bounds in terms of the parameters k, g and $$\lambda $$ . We also determine the orders of the smallest $$egr(v,k,g,\lambda )$$ -graphs for some specific parameters $$(k,g,\lambda )$$ , and address the problem of the smallest possible orders of bipartite edge-girth-regular graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|