Vertex-transitive graph
This article defines a property that can be evaluated to true/false for any undirected graph, and is invariant under graph isomorphism. Note that the term "undirected graph" as used here does not allow for loops or parallel edges, so there can be at most one edge between two distinct vertices, the edge is completely described by the vertices it joins, and there can be no edge from a vertex to itself.
View other such properties
Definition
An undirected graph is termed a vertex-transitive graph if its automorphism group acts transitively on its vertex set. By convention, we may assume that the graph with no vertices is vertex-transitive, though it's better to avoid using the term for such graphs.
Relation with other properties
Stronger properties
| Property | Meaning | Proof of implication | Proof of strictness (reverse implication failure) | Intermediate notions |
|---|---|---|---|---|
| symmetric graph |
Weaker properties
| Property | Meaning | Proof of implication | Proof of strictness (reverse implication failure) | Intermediate notions |
|---|---|---|---|---|
| regular graph |
Invariants associated with vertices
There are many invariants associated with vertices of graphs, such as the degree of a vertex and the eccentricity of a vertex (the latter makes sense only in connected graphs and is finite only in a graph of finite diameter). If the graph is vertex-transitive, then any invariant, if it makes sense, must take the same value at all vertices of the graph.