Seminár z teórie grafov - Dávid Wilsch (3.11.2022)
vo štvrtok 3.11.2022 o 9:50 hod. v miestnosti M/213
Od: Martin Škoviera
Prednášajúci: Dávid Wilsch
Názov: On McKay-Miller-Širáň graphs
Termín: 3.11.2022, 9:50 hod., M 213
The degree-diameter problem is to determine the largest number of vertices in a graph with a given degree and diameter. There is a restricted version of this problem which asks for the largest vertex transitive graph with prescribed parameters. McKay, Miller and Širáň used voltage graphs to construct a family of graphs of diameter 2, degree (3q-r)/2 and order 2*q^2, where q is a prime power congruent to r mod 4 and r is -1, 0 or 1. McKay-Miller-Širáň are vertex transitive for r=1 while for the other two values of r they are highly symmetric but not vertex transitive. Later Šiagiová found a simpler voltage graph construction for the vertex transitive McKay-Miller-Širáň graphs, using base graphs with just two vertices - dipoles. Also, Hafner described all three families geometrically by using incidence graphs of finite affine planes.
We present the results of Šiagiová and Hafner and use them to show that all McKay-Miller-Širáň graphs can be constructed as lifts of dipoles.