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

From MaRDI portal
Added link to MaRDI item.
Import240304020342 (talk | contribs)
Set profile property.
 
(2 intermediate revisions by one other user not shown)
Property / author
 
Property / author: Felix Lazebnik / rank
Normal rank
 
Property / author
 
Property / author: Q917018 / rank
Normal rank
 
Property / author
 
Property / author: Andrew J. Woldar / rank
Normal rank
 
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
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank

Latest revision as of 03:07, 5 March 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
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references