# 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.