Upper Bounds on the Order of Cages

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


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.