However, care must be taken with this definition since arc-transitive or a 1-arc-transitive graphs are sometimes also known as symmetric graphs (Godsil
and Royle 2001, p. 59). This can be especially confusing given that there exist
graphs that are symmetric in the sense of vertex-
and edge-transitive, but not arc-transitive.
In other words, graphs exist for which any edge can be mapped to any other--but in
only one of the two possible ways. Such graphs were first considered by Tutte (1966),
who showed that any such graph must be regular of
even degree. The first examples were given by Bouwer (1970), whose smallest example
had 54 vertices was quartic. Dolye (1976) and Holt
(1981) subsequently and independently discovered a beautiful quartic
symmetric graph on 27 vertices, known as the Doyle
graph (or sometimes the Holt graph), that is not arc-transitive.
This graph can be obtained from Bouwer's 54-vertex graph by identifying pairs of
diametrically opposed vertices (Doyle 1998).
Bouwer, Z. "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull.13, 231-237, 1970.Chao,
C.-Y. "On the Classification of Symmetric Graphs with a Prime Number of Vertices."
Trans. Amer. Math. Soc.158, 247-256, 1971.Cheng, Y. and
Oxley, J. "On Weakly Symmetric Graphs of Order Twice a Prime." J. Combin.
Th. Ser. B42, 196-211, 1987.Doyle, P. G. On Transitive
Graphs. Senior Thesis. Cambridge, MA, Harvard College, April 1976.Doyle,
P. "A 27-Vertex Graph That Is Vertex-Transitive and Edge-Transitive But Not
L-Transitive." October 1998. http://hilbert.dartmouth.edu/~doyle/docs/bouwer/bouwer/bouwer.html.Godsil,
C. and Royle, G. Algebraic
Graph Theory. New York: Springer-Verlag, 2001.Harary, F. "Symmetric
Graphs" and "Highly Symmetric Graphs." Graph
Theory. Reading, MA: Addison-Wesley, pp. 171-175, 1994.Holt,
D. F. "A Graph Which Is Edge Transitive But Not Arc Transitive." J.
Graph Th.5, 201-204, 1981.Holton, D. A. and Sheehan,
J. The
Petersen Graph. Cambridge, England: Cambridge University Press, 1993.Praeger,
C.; Wang, R. J.; and Xu, M. Y. "Symmetric Graphs of Order a Product
of Two Distinct Primes." J. Combin. Th. Ser. B58, 299-318, 1993.Skiena,
S. Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, 1990.Sloane, N. J. A. Sequence A087145
in "The On-Line Encyclopedia of Integer Sequences."Tutte,
W. T. Connectivity
in Graphs. Toronto, CA: University of Toronto Press, 1966.Wang,
R. J. and Xu, M. Y. "A Classification of Symmetric Graphs of Order
." J. Combin. Th. Ser. B58,
197-216, 1993.
, 2, ... nodes are 1, 2, 2, 4, 3, 7, 3, 9, ..., a few of
which are illustrated above. These are the complete
graph 
;
cycle graph 
, 
; 
, 
; 
, circulant graph 
, 
, octahedral graph,
and 
.
)
(utility graph)
." J. Combin. Th. Ser. B 58,
197-216, 1993.