Seminár z teórie grafov - Róbert Jajcay (31.3.2022)
vo štvrtok 31.3.2022 o 9:50 hod. v miestnosti M/213
Od: Martin Škoviera
Prednášajúci: Róbert Jajcay
Názov: Using bi-coset graphs to construct small regular and biregular graphs
Termín: 31.3.2022, 9:50 hod., M 213
A bi-coset graph is a bipartite graph with its two partite sets consisting of the cosets of two subgroups of a given group G, and the adjacency determined by non-empty intersection. Bi-coset graphs constitute a classical object of algebraic graph theory and have been studied in various contexts (often with regard to their symmetries). )
In our talk, bi-coset graphs are revisited with the aim of using them in connection with the Cage Problem - the problem of finding a smallest k-regular graph of girth g - and its generalization - the problem of finding a smallest biregular graph of girth g with the vertices of degrees m,n. The girth of a bi-coset graph is shown to be related to the existence of special alternating sequences of elements from H and K, and k-regular bi-coset graphs of arbitrary large girths are shown to exist for all k >= 2. Bi-coset graphs are shown to be particularly suitable for constructions of bipartite biregular graphs which are biregular graphs in which each of the two sets making the graph bipartite consists of vertices of the same degree.
A few bipartite biregular bi-coset graphs constructed by this method can be shown to be of the smallest order among all bipartite biregular graphs with the same parameters. Interestingly, one of such constructions starts from prime pairs of the form p, 6p+1.
The results discussed in this talk come from a joint paper with S. Gyurki, J. Siran and Y. Wang. This is the first of a series of two talks on the topic, with the second talk delivered by S. Gyurki.