New upper bounds on the order of cages (Q1378551): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Felix Lazebnik / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Vasiliy A. Ustimenko / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Andrew J. Woldar / rank | |||
Normal rank |
Revision as of 15:07, 12 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | New upper bounds on the order of cages |
scientific article |
Statements
New upper bounds on the order of cages (English)
0 references
15 February 1998
0 references
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.
0 references
girth
0 references
cage
0 references
bounds
0 references