New upper bounds on the order of cages

F. Lazebnik ; V. A. Ustimenko ; A. J. Woldar

The electronic journal of combinatorics, The Wilf Festschrift volume, Tome 4 (1997) no. 2

Résumé

Let $ { k\ge 2}$ and $ {g\ge3}$ be integers. A $ {(k,g)}$-graph is a $ {k}$-regular graph with girth (length of a smallest cycle) exactly $ {g}$. A $ {(k,g)}$-cage is a $ {(k,g)}$-graph of minimum order. Let $ {v(k,g)}$ be the order of a $ {(k,g)}$-cage. The problem of determining $ {v(k,g)}$ is unsolved for most pairs $ {(k,g)}$ and is extremely hard in the general case. It is easy to establish the following lower bounds for $ {v(k,g)}$: $ {v(k,g)\ge} {{k(k-1)^{(g-1)/2}-2}\over {k-2}}$ for $ {g}$ odd, and $ {v(k,g)\ge} { {2(k-1)^{g/2}-2}\over {k-2}}$ for $ {g}$ even. The best known upper bounds are roughly the squares of the lower bounds. In this paper we establish general upper bounds on $ {v(k,g)}$ which are roughly the 3/2 power of the lower bounds, and we provide explicit constructions for such $ {(k,g)}$-graphs.

Détail

DOI : 10.37236/1328

Classification : 05C35, 05C38, 05D99
Mots-clés : girth, cage, bounds