TOPICS
Search

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 P_2, the Petersen graph F_(010)A, the Coxeter graph F_(028)A, 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).

Vertex-TransitiveGraphs

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

Vertex-TransitiveConnectedGraphs

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


See also

Arc-Transitive Graph, Automorphism Group, Cayley Graph, Cubic Vertex-Transitive Graph, Edge-Transitive Graph, Folkman Graph, Gray Graph, Group Orbit, Nonhamiltonian Graph, Nonhamiltonian Vertex-Transitive Graph, Quartic Vertex-Transitive Graph, Semisymmetric Graph, Symmetric Graph, Transitive Group

Explore with Wolfram|Alpha

References

Bermond, J.-C. "Hamiltonian Graphs." Ch. 6 in Selected Topics in Graph Theory (Ed. L. W. Beineke and R. J. Wilson). London: Academic Press, pp. 127-167, 1979.Chiang, W.-K. and Chen, R.-J. "The (n,k)-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.Godsil, C. and Royle, G. "Hamilton Paths and Cycles." C§3.6 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 45-47, 2001.Gould, R. J. "Updating the Hamiltonian Problem--A Survey." J. Graph Th. 15, 121-157, 1991.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.Mütze, T. "On Hamilton Cycles in Graphs Defined by Intersecting Set Systems." Not. Amer. Soc. 74, 583-592, 2024.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.

Referenced on Wolfram|Alpha

Vertex-Transitive Graph

Cite this as:

Weisstein, Eric W. "Vertex-Transitive Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Vertex-TransitiveGraph.html

Subject classifications