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