Vertex-transitive graph

A graph is vertex-transitive if, for every pair of vertices, some automorphism maps one to the other. Thus every vertex has the same structural position within the graph.

Graph automorphism: A bijection from a graph’s vertices to itself that preserves adjacency. Vertex-transitivity requires automorphisms that carry each chosen vertex to any other.
Orbit-stabilizer theorem: A theorem relating the size of a group orbit to the sizes of the group and a point’s stabilizer. It connects the number of vertices to the automorphisms fixing one vertex.
Cycle graph: A graph whose vertices form one closed path, with each vertex joined to its two neighbors. Rotations carry any vertex of a cycle to any other.
Edge-transitive graph: A graph whose automorphism group acts transitively on its edges. Edge-transitivity concerns edges, not whether all vertices lie in one orbit.
Automorphism group: The group of all structure-preserving bijections of a mathematical object to itself. Its action on vertices determines whether the graph is vertex-transitive.
Vertex stabilizer: The subgroup of graph automorphisms that fixes a specified vertex. In a vertex-transitive graph, stabilizers of different vertices have equal size.
Complete graph: A simple graph in which every pair of distinct vertices is joined by an edge. Every permutation of its vertices is an automorphism.
Arc-transitive graph: A graph whose automorphisms act transitively on ordered adjacent vertex pairs. Arc-transitivity is stronger than vertex-transitivity because it also controls directed edge positions.
Group action: A rule describing how the elements of a group transform a set while respecting group composition. Transitivity is the property that this action has a single orbit on vertices.
Cayley graph: A graph encoding a group’s generators as edges between its elements. Left multiplication makes every Cayley graph vertex-transitive.

Linked from 6 pages