Vertex-Transitive Graph

A vertex-transitive graph, also called a point-symmetric graph by Harary and Palmer (1973, p. 263) and sometimes a node symmetric graph (Chiang and Chen 1995), is a graph such that every pair of vertices is equivalent under some element of its automorphism group. More explicitly, a vertex-transitive graph is a graph whose automorphism group is transitive (Holton and Sheehan 1993, p. 27). Thus no graph vertex is distinguished from any other by the structure of the whole graph. Having isomorphic neighborhood graphs at every graph vertex is not sufficient.

Another way of characterizing a vertex-transitive graph is as a graph for which the automorphism group has a single group orbit on its vertices (so, for a finite graph of order , the list of group orbit lengths is ).

A graph may be tested to determine if it is vertex-transitive in the Wolfram Language using VertexTransitiveGraphQ[g].

A graph in which every edge has the same local environment, so that no graph edge can be distinguished from any other, is said to be edge-transitive. A connected undirected graph is edge-transitive if its line graph is vertex-transitive.

All vertex-transitive graphs are regular, but not necessarily vice versa. A regular graph that is edge-transitive but not vertex-transitive is called a semisymmetric graph. Under the vertex-and-edge-transitive convention used in this work, a graph that is both edge-transitive and vertex-transitive is a symmetric graph (Holton and Sheehan 1993, pp. 209-210). The arc-transitive convention instead reserves that name for arc-transitive graphs.

The Lovász conjecture asserts that without exception, every connected vertex-transitive graph is traceable.

Furthermore, there are exactly five known connected nonhamiltonian vertex-transitive graphs, namely the path graph , the Petersen graph , the Coxeter graph , the triangle-replaced Petersen, and the triangle-replaced Coxeter graph. As attributed by Gould (1991) citing Bermond (1979), Thomassen conjectured that all other connected vertex-transitive graphs are Hamiltonian (cf. Godsil and Royle 2001, p. 45; Mütze 2024).

The numbers of nonisomorphic simple graphs with , 2, ... nodes that are vertex-transitive are 1, 2, 2, 4, 3, 8, 4, 14, 9, ... (OEIS A006799; McKay and Royle 1990, Colbourn and Dinitz 1996).

The numbers of nonisomorphic simple graphs on nodes that are connected and vertex-transitive for , 2, ... are 1, 1, 1, 2, 2, 5, 3, 10, 7, ... (OEIS A006800; McKay and Royle 1990).

Ma and Zhao (2026, p. 1) proved that every finite connected vertex-transitive graph on vertices has graph circumference at least for an absolute constant . For all sufficiently large vertex degrees , the bound improves to .