Vertex-transitive graph
In the mathematical field of graph theory, an automorphism is a permutation of the vertices such that edges are mapped to edges and non-edges are mapped to non-edges. A graph is a vertex-transitive graph if, given any two vertices and of, there is an automorphism such that
In other words, a graph is vertex-transitive if its automorphism group acts transitively on its vertices. A graph is vertex-transitive if and only if its graph complement is, since the group actions are identical.
Every symmetric graph without isolated vertices is vertex-transitive, and every vertex-transitive graph is regular. However, not all vertex-transitive graphs are symmetric, and not all regular graphs are vertex-transitive.
Finite examples
Finite vertex-transitive graphs include the symmetric graphs. The finite Cayley graphs are also vertex-transitive, as are the vertices and edges of the Archimedean solids. Potočnik, Spiga and Verret have constructed a census of all connected cubic vertex-transitive graphs on at most 1280 vertices.Although every Cayley graph is vertex-transitive, there exist other vertex-transitive graphs that are not Cayley graphs. The most famous example is the Petersen graph, but others can be constructed including the line graphs of edge-transitive non-bipartite graphs with odd vertex degrees.
Properties
The edge-connectivity of a connected vertex-transitive graph is equal to the degree d, while the vertex-connectivity will be at least 2/3.If the degree is 4 or less, or the graph is also edge-transitive, or the graph is a minimal Cayley graph, then the vertex-connectivity will also be equal to d.
Infinite examples
Infinite vertex-transitive graphs include:- infinite paths
- infinite regular trees, e.g. the Cayley graph of the free group
- graphs of uniform tessellations, including all regular polygons|tilings by regular polygons]
- infinite Cayley graphs
- the Rado graph