Fakulta matematiky, fyziky
a informatiky
Univerzita Komenského v Bratislave

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

01. 11. 2022 20.32 hod.
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. 

Stránka seminára