TOPICS
Search

Symmetric Graph


A symmetric graph is a graph that is both edge- and vertex-transitive (Holton and Sheehan 1993, p. 209).

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

A regular graph that is edge-transitive but not vertex-transitive is called a semisymmetric graph.

Neither the graph complement nor the line graph of a symmetric graph is necessarily symmetric.

SymmetricGraphs

Symmetric graphs are always regular graphs. The number of symmetric graphs on n=1, 2, ... nodes are 1, 2, 2, 4, 3, 7, 3, 9, ..., a few of which are illustrated above. These are the complete graph K_3; cycle graph C_4, K_4; C_5, K_5; C_6, circulant graph Ci_6(1,3), Ci_6(2), octahedral graph, and K_6.

A list of other named symmetric graphs is given in the table below.


See also

Arc-Transitive Graph, Automorphism Group, Bouwer Graph, Cubic Symmetric Graph, Doyle Graph, Edge-Transitive Graph, Graph Automorphism, Identity Graph, Quartic Symmetric Graph, Vertex-Transitive Graph

Explore with Wolfram|Alpha

References

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. B 42, 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. B 58, 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 3p." J. Combin. Th. Ser. B 58, 197-216, 1993.

Referenced on Wolfram|Alpha

Symmetric Graph

Cite this as:

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

Subject classifications