Seminar of Graph Theory - Pavol Kollar (12.11.2026)
Thursday 12.11.2026 at 9:50, Lecture room M 213
Pavol Kollár:
What do r-regular families tell us about vertex-transitive graphs
Abstract:
Graphs that have a high number of symmetries are beautiful and also very interesting to study. We will focus on vertex-transitive graphs, which can be thought of as "the graph looks exactly the same, no matter which vertex we look at it from". But not all vertex-transitive graphs are created equal and for us the baseline will be made up of Cayley graphs, which are a well-known and widely studied proper subclass of vertex-transitive graphs. The 10-vertex Petersen graph is the smallest example of a graph that is vertex-transitive, but is not Cayley. Gauyacq showed that the Petersen graph is in fact a quasi-Cayley graph and this notion was later generalised by Jajcay and Jones with "Cayley deficiency" and "quasi-Cayley deficiency". Jajcay and Jones also observed and proved that the 20-vertex Dodecahedron graph is not a Cayley graph nor a quasi-Cayley graph, because both its deficiency values are equal to 3.
In our work we will investigate what deficiency values are obtained by which graphs on a small number of vertices - enhancing the census of vertex-transitive graphs by Holt and Royle - as well as determine a few "record graphs" among these with respect to the deficiency values.