Structure and Properties of Vertex-Transitive Graphs

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.

Back to all abstracts