Editing Edge-transitive graph

{{short description|Graph where all pairs of edges are automorphic}}
{{about|graph theory|edge transitivity in geometry|Edge-transitive}}
{{Graph families defined by their automorphisms}}

In the [[mathematics|mathematical]] field of [[graph theory]], an  '''edge-transitive graph''' is a [[Graph (discrete mathematics)|graph]] {{mvar|G}} such that, given any two edges {{math|''e''{{sub|1}}}} and {{math|''e''{{sub|2}}}} of {{mvar|G}}, there is an [[Graph automorphism|automorphism]] of {{mvar|G}} that [[Map (mathematics)|maps]] {{math|''e''{{sub|1}}}} to {{math|''e''{{sub|2}}}}.<ref name="biggs">{{cite book | author=Biggs, Norman | title=Algebraic Graph Theory | edition=2nd | location=Cambridge | publisher=Cambridge University Press | year=1993 | page=118 | isbn=0-521-45897-8}}</ref>

In other words, a graph is edge-transitive if its [[automorphism group]] acts [[Group action#Remarkable properties of actions|transitively]] on its edges.

==Examples and properties==
[[Image:Gray graph 2COL.svg|thumb|200px|The [[Gray graph]] is edge-transitive and [[regular graph|regular]], but not [[vertex-transitive graph|vertex-transitive]].]]

The number of connected simple edge-transitive graphs on n vertices is 1, 1, 2, 3, 4, 6, 5, 8, 9, 13, 7, 19, 10, 16, 25, 26, 12, 28 ... {{OEIS|A095424}}

Edge-transitive graphs include all [[symmetric graph|symmetric graphs]], such as the vertices and edges of the [[cube]].<ref name="biggs" />  Symmetric graphs are also [[vertex-transitive graph|vertex-transitive]] (if they are [[Connectivity (graph theory)|connected]]), but in general edge-transitive graphs need not be vertex-transitive. Every [[Connectivity (graph theory)|connected]] edge-transitive graph that is not vertex-transitive must be [[bipartite graph|bipartite]],<ref name="biggs" /> (and hence can be [[Graph coloring|colored]] with only two colors), and either semi-symmetric or [[biregular graph|biregular]].<ref name="ls03">{{citation
 | last1 = Lauri | first1 = Josef
 | last2 = Scapellato | first2 = Raffaele
 | isbn = 9780521529037
 | pages = 20–21
 | publisher = Cambridge University Press
 | series = London Mathematical Society Student Texts
 | title = Topics in Graph Automorphisms and Reconstruction
 | url = https://books.google.com/books?id=hsymFm0E0uIC&pg=PA20
 | year = 2003}}.</ref>

Examples of edge but not vertex transitive graphs include the [[complete bipartite graph]]s <math>K_{m,n}</math> where m ≠ n, which includes the star graphs <math>K_{1,n}</math>. For graphs on n vertices, there are (n-1)/2 such graphs for odd n and (n-2) for even n.
Additional edge transitive graphs which are not symmetric can be formed as subgraphs of these complete bi-partite graphs in certain cases. Subgraphs of complete bipartite graphs K<sub>m,n</sub> exist when m and n share a factor greater than 2. When the greatest common factor is 2, subgraphs exist when 2n/m is even or if m=4 and n is an odd multiple of 6.<ref>{{cite journal |last1=Newman |first1=Heather A. |last2=Miranda |first2=Hector |last3=Narayan |first3=Darren A |title=Edge-transitive graphs and combinatorial designs |journal=Involve: A Journal of Mathematics |year=2019 |volume=12 |issue=8 |pages=1329–1341 |doi=10.2140/involve.2019.12.1329 |arxiv=1709.04750 |s2cid=119686233 }}</ref> So edge transitive subgraphs exist for K<sub>3,6</sub>, K<sub>4,6</sub> and K<sub>5,10</sub> but not K<sub>4,10</sub>. An alternative construction for some edge transitive graphs is to add vertices to the midpoints of edges of a symmetric graph with v vertices and e edges, creating a bipartite graph with e vertices of order 2, and v of order 2e/v.

An edge-transitive graph that is also [[regular graph|regular]], but still not vertex-transitive, is called [[semi-symmetric graph|semi-symmetric]].  The [[Gray graph]], a cubic graph on 54 vertices, is an example of a regular graph which is edge-transitive but not vertex-transitive. The [[Folkman graph]], a quartic graph on 20 vertices is the smallest such graph.

The [[k-vertex-connected graph|vertex connectivity]] of an edge-transitive graph always equals its [[degree (graph theory)|minimum degree]].<ref>{{citation
 | last = Watkins | first = Mark E.
 | doi = 10.1016/S0021-9800(70)80005-9
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 266804
 | pages = 23–29
 | title = Connectivity of transitive graphs
 | volume = 8
 | year = 1970| doi-access = 
 }}</ref>

== See also ==
* [[Edge-transitive]] (in geometry)

==References==
{{reflist}}

== External links ==
* {{MathWorld | urlname=Edge-TransitiveGraph | title=Edge-transitive graph }}

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