New upper bounds on the order of cages (Q1378551): Difference between revisions

Summary: Let \(k\geq 2\) and \(g\geq3\) 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)\geq {{k(k-1)^{(g-1)/2}-2}\over {k-2}}\) for \(g\) odd, and \(v(k,g)\geq { {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.