Editing Symmetric graph (section)

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