Home > Timetable > Contribution details

Contribution

Upper bounds for the order of cages

Speakers

  • Dr. Sara Sabrina ZEMLJIC

Primary authors

Co-authors

Content

A $(k,g)$-graph is a simple undirected $k$-regular graph with girth $g$. A $(k,g)$-cage is a $(k,g)$-graph with the least possible number of vertices. Cages have been studied quite intensively yet for most pairs $(k,g)$ the corresponding cages are still unknown.

There is an obvious lower bound on the order of a $(k,g)$-cage, called the Moore bound (i.e., the number of vertices needed for a $(k,g)$-cage). There are several constructions for the upper bound for it, but often the upper bound is relatively far from the Moore bound.

In the talk I will discuss known upper bounds together with a new method for shortening the gap between the Moore bound and an upper bound on the order of a $(k,g)$-cage.