Symmetric graph
From Wikipedia, the free encyclopedia
In graph theory, a graph G is symmetric (or arc-transitive) if, given any two pairs of linked vertices u1−−v1 and u2−−v2 of G, there is an automorphism
- f : V(G) → V(G)
such that
- f(u1) = u2 and f(v1) = v2.[1]
In other words, a graph is symmetric if its automorphism group acts transitively upon ordered pairs of linked vertices (that is, upon edges considered as having a direction).[2] Such a graph is sometimes also called 1-arc-transitive[2] or flag-transitive.[3]
By definition (ignoring u1 and u2), a symmetric graph without isolated vertices must also be vertex transitive.[1] Since the definition above maps one edge to another, a symmetric graph must also be edge transitive. However, an edge-transitive graph need not be symmetric, since a−−b might map to c−−d, but not to d−−c. Semi-symmetric graphs, for example, are edge-transitive and regular, but not vertex-transitive. Graphs also exist that are vertex-transitive and edge-transitive but not symmetric.[4] However, a vertex-transitive and edge-transitive graph of odd degree will always be symmetric.[3]
| Some graph families defined by their automorphisms | ||
| distance-transitive |  |
distance-regular |
 |
||
| symmetric (arc-transitive) | |
edge-transitive |
| (if connected) |
||
| vertex-transitive |  |
Cayley graph |
|
||
| regular | ||
A distance-transitive graph is one where instead of considering pairs of linked vertices (i.e. vertices a distance of 1 apart), the definition covers two pairs of vertices, each the same distance apart. Such graphs are automatically symmetric, by definition.[1]
Contents |
[edit] Examples of Symmetric Graphs
Combining the symmetry condition with the restriction that graphs be cubic (i.e. all vertices have degree 3) yields quite a strong condition, and such graphs are rare enough to be listed. The Foster census and its extensions provide such lists.[5] The Foster census was begun by professor Ronald M. Foster, and in 1988 the then current Foster census (listing all cubic symmetric graphs up to 512 vertices) was published in book form.[6] The beginning of the list consists of the nine cubic symmetric graphs with up to 20 vertices:[7]
| Vertices | Graph |
| 4 | The complete graph K4 |
| 6 | The complete bipartite graph K3,3 |
| 8 | The vertices and edges of the cube |
| 10 | The Petersen graph |
| 14 | The Heawood graph |
| 16 | The Möbius–Kantor graph |
| 18 | The Pappus graph |
| 20 | The Desargues graph |
| 20 | The vertices and edges of the dodecahedron |
Eight of these nine graphs are distance-transitive; the exception is the Möbius–Kantor graph, which is not distance-transitive.
Non-cubic symmetric graphs include cycle graphs (of degree 2), complete graphs (of degree 4 or more when there are 5 or more vertices), hypercube graphs (of degree 4 or more when there are 16 or more vertices), and the graphs formed by the vertices and edges of the octahedron, icosahedron, cuboctahedron, and icosidodecahedron. The Rado graph forms an example of a symmetric graph with infinitely many vertices and infinite degree.
[edit] See also
[edit] References
- ^ a b c Biggs, Norman (1993). Algebraic Graph Theory (2nd ed. ed.). Cambridge: Cambridge University Press. p. 118. ISBN 0-521-45897-8.
- ^ a b Godsil, Chris, and Royle, Gordon (2001). Algebraic Graph Theory. New York: Springer. p. 59. ISBN 0-387-95220-9.
- ^ a b Babai, L (1996), "Automorphism groups, isomorphism, reconstruction", in Graham, R; Groetschel, M; Lovasz, L, Handbook of Combinatorics, Elsevier
- ^ Bouwer, Z. "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull. 13, 231-237, 1970.
- ^ Marston Conder, Trivalent symmetric graphs on up to 768 vertices, J. Combin. Math. Combin. Comput, vol. 20, pp. 41-63
- ^ "The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs", by Ronald M. Foster, I.Z. Bouwer, W.W. Chernoff, B. Monson and Z. Star (1988) ISBN 0919611192
- ^ Biggs, p. 148
[edit] External links
- Cubic symmetric graphs (The Foster Census). Data files for all cubic symmetric graphs up to 768 vertices, and some cubic graphs with up to 1000 vertices. Gordon Royle, updated February 2001, retrieved 2009-04-18.
