Upper bounds for the order of cages

Not scheduled
15m
UP FHS (Koper)

UP FHS

Koper

Titov trg 5,Koper

Speaker

Dr Sara Sabrina Zemljic (Comenius University Bratislava)

Description

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.

Primary author

Dr Sara Sabrina Zemljic (Comenius University Bratislava)

Co-author

Prof. Robert Jajcay (Comenius University, Bratislava, and University of Primorska, Koper)

Presentation Materials

There are no materials yet.