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).

Lovász (1970) conjectured that every connected vertex-transitive graph is traceable (Gould, p. 33). This conjecture was subsequently verified for several special orders and classes. Furthermore, with a few notable exceptions, such graphs were also shown to be Hamiltonian. There are currently only five known connected nonhamiltonian vertex-transitive graphs.

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).

REFERENCES

Chiang, W.-K. and Chen, R.-J. "The -Star Graph: A Generalized Star Graph." Information Proc. Lett. 56, 259-264, 1995.

Colbourn, C. J. and Dinitz, J. H. (Eds.). CRC Handbook of Combinatorial Designs. Boca Raton, FL: CRC Press, p. 649, 1996.

Holton, D. A. and Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, 1993.

Lauri, J. and Scapellato, R. Topics in Graph Automorphisms and Reconstruction. Cambridge, England: Cambridge University Press, 2003.Lovász, L. Problem 11 in "Combinatorial Structures and Their Applications." In Proc. Calgary Internat. Conf. Calgary, Alberta, 1969. London: Gordon and Breach, pp. 243-246, 1970.

McKay, B. D. and Praeger, C. E. "Vertex-Transitive Graphs Which Are Not Cayley Graphs. I." J. Austral. Math. Soc. Ser. A 56, 53-63, 1994.

McKay, B. D. and Royle, G. F. "The Transitive Graphs with at Most 26 Vertices." Ars Combin. 30, 161-176, 1990.

Royle, G. "Cubic Symmetric Graphs (The Foster Census): Hamiltonian Cycles." http://school.maths.uwa.edu.au/~gordon/remote/foster/#hamilton.Royle, G. "Transitive Graphs." http://school.maths.uwa.edu.au/~gordon/trans/.

Sloane, N. J. A. Sequences A006799/M0302 and A006800/M0345 in "The On-Line Encyclopedia of Integer Sequences."Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.