Štefánia Glevitzká: Vertex-transitive closures of simple graphs

Štefánia Glevitzká (Comenius University Bratislava)

Abstract: A graph is vertex-transitive if for every pair of vertices u and v there exists an automorphism of the graph that maps u to v. A vertex-transitive closure of a graph G is any vertex-transitive graph containing G as a spanning subgraph. The vertex-transitive number of G is the smallest possible degree of its vertex-transitive closure. These two concepts were first introduced by Bachratý and Širáň in 2015 as a follow-up to their and some earlier observations regarding polarity graphs. In this talk, we introduce these concepts and the known and new observations on polarity graphs. We bound and in some cases also determine vertex-transitive numbers for specific classes of graphs, prove some general observations and discuss a possible relation to automorphism groups.