Seminar of Graph Theory - Dávid Wilsch (3.11.2022)
Thursday 3.11.2022 at 9:50, Lecture room M/213
Dávid Wilsch:
On McKay-Miller-Širáň graphs
Abstract:
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.