Vertex-Transitive Graph

A vertex-transitive graph, also sometimes called 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). Informally speaking, a graph is vertex-transitive if every vertex has the same local environment, so that no vertex can be distinguished from any other based on the vertices and edges surrounding it.

Another way of characterizing a vertex-transitive graph is as a graph for which the automorphism group has a single group orbit (i.e., the orbit lengths of its automorphism group are a single number).

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 edge can be distinguished from any other, is said to be edge-transitive. A undirceted connected 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. In contrast, any graph that is both edge-transitive and vertex-transitive is called a symmetric graph (Holton and Sheehan 1993, pp. 209-210).

The Lovász assrts 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 simple graphs with , 2, ... nodes that are vertex-transitive are 1, 2, 2, 4, 3, 8, 4, 14, 9, ... (OEIS A006799; McKay 1990; Colbourn and Dinitz 1996).

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