Structure and Properties of Vertex-Transitive Graphs
Robert Jajcay
Comenius University, Bratislava, and University of Primorska
PDF
Minisymposium: STRUCTURE AND PROPERTIES OF VERTEX-TRANSITIVE GRAPHS
Content: Vertex-transitive graphs have many regularity properties, and look the same in the neighborhoods of all of their vertices. Consequently, the number of any small induced subgraphs, such as cycles or cliques, containing any fixed vertex of a vertex-transitive graph must be the same for each vertex of the graph. While this observation can be used for a quick criterion to show that a graph is not vertex-transitive, it can also be used for argueing the non-existence of certain vertex-transitive graphs. We demonstrate such techniques for two well-known problems from extremal graph theory restricted to the class of vertex-transitive graphs, namely the Cage Problem and the Degree/Diameter Problem. We also dicuss some recent methods for constructing vertex-transitive graphs with prescribed degree, girth, or diameter, and address the problem of the cycle length distribution of vertex-transitive graphs.