Seminár z teórie grafov - Róbert Jajcay (30.9.2021)
vo štvrtok 30.9.2021 o 9:50 hod. v miestnosti M/213
Od: Martin Škoviera
Prednášajúci: Róbert Jajcay
Názov: Biregular Cages
Termín: 30.9.2021, 9:50 hod., M 213
The Cage Problem - the problem of finding a smallest k-regular graph of girth g, i.e., the (k,g)-cage - is well known to be very hard and the exact orders of cages are known for very few parameter pairs (k,g). One possible approach to understanding structural properties of cages includes considering biregular graphs that contain vertices of two degrees, m and n, and generalizing the Cage Problem by looking for smallest graphs of girth g containing vertices of the two degrees m and n, the (m,n;g)-cages. In the case of odd girths, results of this approach differ quite a bit from the regular Cage Problem as the orders of biregular (m,n;g)-cages are determined for all odd girths g and degree pairs m,n in which m is considerably smaller than n. The even girth case is still wide open, and has been therefore restricted to bipartite biregular graphs in which the two bipartite sets consist exclusively of vertices of one of the degrees (regular cages of even girth are also conjectured to be bipartite). We survey the most resent results on biregular and bipartite biregular cages, present some improved lower bounds, and discuss an interesting connection between bipartite biregular cages and t-designs.