Editing Symmetric graph

{{short description|Graph in which all ordered pairs of linked nodes are automorphic}}
[[File:Petersen1 tiny.svg|thumb|200px|The [[Petersen graph]] is a ([[Cubic graph|cubic]]) symmetric graph.  Any pair of adjacent vertices can be mapped to another by an [[Graph automorphism|automorphism]], since any five-vertex ring can be mapped to any other.]]

In the [[mathematics|mathematical]] field of [[graph theory]], a [[Graph (discrete mathematics)|graph]] {{mvar|G}} is '''symmetric''' or '''arc-transitive''' if, given any two ordered pairs of adjacent [[Vertex (graph theory)|vertices]] <math>(u_1,v_1)</math> and <math>(u_2,v_2)</math> of {{mvar|G}}, there is an [[Graph automorphism|automorphism]]

:<math>f : V(G) \rightarrow V(G)</math>

such that

:<math>f(u_1) = u_2</math> and <math>f(v_1) = v_2.</math><ref name="biggs">{{cite book | author=Biggs, Norman | title=Algebraic Graph Theory | edition=2nd | location=Cambridge | publisher=Cambridge University Press | year=1993 | pages=118–140 | isbn=0-521-45897-8}}</ref>

In other words, a graph is symmetric if its [[automorphism group]] acts [[Group_action#Remarkable properties of actions|transitively]] on [[ordered pair]]s of adjacent vertices (that is, upon edges considered as having a direction).<ref name="godsil">{{cite book |first1=Chris|last1=Godsil|authorlink1=Chris Godsil|first2=Gordon|last2=Royle|authorlink2=Gordon Royle|title=Algebraic Graph Theory|url=https://archive.org/details/algebraicgraphth00gods|url-access=limited| location=New York| publisher=Springer | year=2001 | page=[https://archive.org/details/algebraicgraphth00gods/page/n79 59] | isbn=0-387-95220-9}}</ref> Such a graph is sometimes also called '''{{nowrap|1-arc}}-transitive'''<ref name="godsil"/> or '''flag-transitive'''.<ref name="babai">{{Cite book | first = L | last = Babai | editor-last = Graham | editor-first = R | editor2-last =  Grötschel | editor2-first = M | editor2-link = Martin Grötschel | editor3-last = Lovász | editor3-first = L | title = Handbook of Combinatorics | contribution = Automorphism groups, isomorphism, reconstruction | contribution-url = http://people.cs.uchicago.edu/~laci/handbook/handbookchapter27.pdf | year = 1996 | publisher = Elsevier}}</ref>

By definition (ignoring {{math|''u''{{sub|1}}}} and {{math|''u''{{sub|2}}}}), a symmetric graph without [[isolated vertex|isolated vertices]] must also be [[Vertex-transitive graph|vertex-transitive]].<ref name="biggs" /> Since the definition above maps one edge to another, a symmetric graph must also be [[Edge-transitive graph|edge-transitive]]. However, an edge-transitive graph need not be symmetric, since {{mvar|a—b}} might map to {{mvar|c—d}}, but not to {{mvar|d—c}}. [[Star (graph theory)|Star graphs]] are a simple example of being edge-transitive without being vertex-transitive or symmetric. As a further example, [[semi-symmetric graph]]s are edge-transitive and [[regular graph|regular]], but not vertex-transitive. 

{{Graph families defined by their automorphisms}}

Every [[Connectivity (graph theory)|connected]] symmetric graph must thus be both vertex-transitive and edge-transitive, and the converse is true for graphs of [[parity (mathematics)|odd]] degree.<ref name="babai" />  However, for [[parity (mathematics)|even]] degree, there exist connected graphs which are vertex-transitive and edge-transitive, but not symmetric.<ref>{{cite journal | last1=Bouwer | first1=Z. | title=Vertex and Edge Transitive, But Not 1-Transitive Graphs | journal=[[Canad. Math. Bull.]] | volume=13 | pages=231&ndash;237 | date=1970 | doi=10.4153/CMB-1970-047-8 | doi-access=free}}</ref>  Such graphs are called [[half-transitive graph|half-transitive]].<ref name="handbook">{{cite book |author1=Gross, J.L.  |author2=Yellen, J.  |name-list-style=amp | title=Handbook of Graph Theory | publisher=CRC Press | year=2004| page=491 | isbn=1-58488-090-2}}</ref> The smallest connected half-transitive graph is [[Holt's graph]], with degree 4 and 27 vertices.<ref name="biggs" /><ref>{{Cite journal|title=A graph which is edge transitive but not arc transitive|first=Derek F.|last=Holt|journal=[[Journal of Graph Theory]]|volume=5|issue=2|pages=201–204|year=1981|doi=10.1002/jgt.3190050210}}.</ref> Confusingly, some authors use the term "symmetric graph" to mean a graph which is vertex-transitive and edge-transitive, rather than an arc-transitive graph. Such a definition would include half-transitive graphs, which are excluded under the definition above.

A [[distance-transitive graph]] is one where instead of considering pairs of adjacent 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.<ref name="biggs" />

A {{nowrap|{{mvar|t}}-arc}} is defined to be a [[sequence]] of {{math|''t'' + 1}} vertices, such that any two consecutive vertices in the sequence are adjacent, and with any repeated vertices being more than 2 steps apart. A '''{{nowrap|{{mvar|t}}-transitive}} graph''' is a graph such that the automorphism group acts transitively on {{nowrap|{{mvar|t}}-arcs}}, but not on {{nowrap|({{math|{{mvar|t}} + 1}})-arcs}}.  Since {{nowrap|1-arcs}} are simply edges, every symmetric graph of degree 3 or more must be {{nowrap|{{mvar|t}}-transitive}} for some {{mvar|t}}, and the value of {{mvar|t}} can be used to further classify symmetric graphs.  The cube is {{nowrap|2-transitive}}, for example.<ref name="biggs" />

Note that conventionally the term "symmetric graph" is not complementary to the term "[[asymmetric graph]]," as the latter refers to a graph that has no nontrivial symmetries at all.

==Examples==

<!--Please do not change section heading as "Foster Census" and "Foster census" redirect to it.-->
Two basic families of symmetric graphs for any number of vertices are the [[cycle graph]]s (of degree 2) and the [[complete graph]]s. Further symmetric graphs are formed by the vertices and edges of the regular and quasiregular polyhedra: the [[cube]], [[octahedron]], [[icosahedron]], [[dodecahedron]], [[cuboctahedron]], and [[icosidodecahedron]]. Extension of the cube to n dimensions gives the hypercube graphs (with 2<sup>n</sup> vertices and degree n). Similarly extension of the octahedron to n dimensions gives the graphs of the [[cross-polytope]]s, this family of graphs (with 2n vertices and degree 2n − 2) are sometimes referred to as the [[cocktail party graph]]s - they are complete graphs with a set of edges making a perfect matching removed. Additional families of symmetric graphs with an even number of vertices 2n, are the evenly split [[complete bipartite graph]]s K<sub>n,n</sub> and the [[crown graph]]s on 2n vertices. Many other symmetric graphs can be classified as [[circulant graph]]s (but not all).

The [[Rado graph]] forms an example of a symmetric graph with infinitely many vertices and infinite degree.
===Cubic symmetric graphs===
Combining the symmetry condition with the restriction that graphs be [[Cubic graph|cubic]] (i.e. all vertices have degree 3) yields quite a strong condition, and such graphs are rare enough to be listed. They all have an even number of vertices.  The '''Foster census''' and its extensions provide such lists.<ref>[[Marston Conder]], ''[http://www.math.auckland.ac.nz/~conder/preprints/cubic768.ps Trivalent symmetric graphs on up to 768 vertices],'' J. Combin. Math. Combin. Comput, vol. 20, pp. 41&ndash;63</ref> The Foster census was begun in the 1930s by [[R. M. Foster|Ronald M. Foster]] while he was employed by [[Bell Labs]],<ref>Foster, R. M. "Geometrical Circuits of Electrical Networks." ''[[Transactions of the American Institute of Electrical Engineers]]'' '''51''', 309&ndash;317, 1932.</ref> and in 1988 (when Foster was 92<ref name="biggs"/>) the then current Foster census (listing all cubic symmetric graphs up to 512 vertices) was published in book form.<ref>"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|0-919611-19-2}}</ref>  The first thirteen items in the list are cubic symmetric graphs with up to 30 vertices<ref>Biggs, p. 148</ref><ref name="F26A">Weisstein, Eric W., "[http://mathworld.wolfram.com/CubicSymmetricGraph.html Cubic Symmetric Graph]", from Wolfram MathWorld.</ref> (ten of these are also [[Distance-transitive graph|distance-transitive]]; the exceptions are as indicated):

{| class="wikitable"
|-
!'''Vertices''' !! '''[[Diameter (graph theory)|Diameter]]''' !! '''[[Girth (graph theory)|Girth]]''' !! '''Graph''' !! '''Notes'''
|-
|4 || 1 || 3 || The [[complete graph]] ''K''<sub>4</sub> || distance-transitive, 2-arc-transitive
|-
|6 || 2 || 4 || The [[complete bipartite graph]] ''K''<sub>3,3</sub> || distance-transitive, 3-arc-transitive
|-
|8 || 3 || 4 || The vertices and edges of the [[cube]] || distance-transitive, 2-arc-transitive
|-
|10 || 2 || 5 || The [[Petersen graph]] || distance-transitive, 3-arc-transitive
|-
|14 || 3 || 6 || The [[Heawood graph]] || distance-transitive, 4-arc-transitive
|-
|16 || 4 || 6 || The [[Möbius–Kantor graph]] || 2-arc-transitive
|-
|18 || 4 || 6 || The [[Pappus graph]] || distance-transitive, 3-arc-transitive
|-
|20 || 5 || 5 || The vertices and edges of the [[dodecahedron]] || distance-transitive, 2-arc-transitive
|-
|20 || 5 || 6 || The [[Desargues graph]] || distance-transitive, 3-arc-transitive
|-
|24 || 4 || 6 || The [[Nauru graph]] (the [[generalized Petersen graph]] G(12,5)) || 2-arc-transitive
|-
|26 || 5 || 6 || The [[F26A graph]]<ref name="F26A"/> || 1-arc-transitive
|-
|28 || 4 || 7 || The [[Coxeter graph]] || distance-transitive, 3-arc-transitive
|-
|30 || 4 || 8 || The [[Tutte–Coxeter graph]] || distance-transitive, 5-arc-transitive
|}

Other well known cubic symmetric graphs are the [[Dyck graph]], the [[Foster graph]] and the [[Biggs&ndash;Smith graph]].  The ten distance-transitive graphs listed above, together with the [[Foster graph]] and the [[Biggs&ndash;Smith graph]], are the only cubic distance-transitive graphs.

== Properties ==
The [[Connectivity (graph theory)|vertex-connectivity]] of a symmetric graph is always equal to the [[regular graph|degree]] ''d''.<ref name="babai" /> In contrast, for [[vertex-transitive graph]]s in general, the vertex-connectivity is bounded below by 2(''d''&nbsp;+&thinsp;1)/3.<ref name="godsil" />

A ''t''-transitive graph of degree 3 or more has [[Girth (graph theory)|girth]] at least 2(''t''&nbsp;−&thinsp;1).  However, there are no finite ''t''-transitive graphs of degree 3 or more for&nbsp;''t''&nbsp;≥&nbsp;8.  In the case of the degree being exactly 3 (cubic symmetric graphs), there are none for&nbsp;''t''&nbsp;≥&nbsp;6.

==See also==
*[[Algebraic graph theory]]
*[[Gallery of named graphs#Symmetric graphs|Gallery of named graphs]]
*[[Regular map (graph theory)|Regular map]]

==References==
{{reflist}}

==External links==
*[https://web.archive.org/web/20081004205049/http://people.csse.uwa.edu.au/gordon/remote/foster/ 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.
*[http://www.math.auckland.ac.nz/~conder/symmcubic10000list.txt Trivalent (cubic) symmetric graphs on up to 10000 vertices]. [[Marston Conder]], 2011.

[[Category:Algebraic graph theory]]
[[Category:Graph families]]
[[Category:Regular graphs]]