Edge-transitive graph

In the mathematical field of graph theory, an edge-transitive graph is a graph G such that, given any two edges e1 and e2 of G, there is an automorphism of G that maps e1 to e2.[1]

Graph families defined by their automorphisms
distance-transitive → distance-regular ← strongly regular
↓
symmetric (arc-transitive) ← t-transitive, t ≥ 2 skew-symmetric
↓
(if connected)
vertex- and edge-transitive		 → edge-transitive and regular → edge-transitive
↓ ↓ ↓
vertex-transitive → regular → (if bipartite)
biregular
↑
Cayley graph ← zero-symmetric asymmetric

In other words, a graph is edge-transitive if its automorphism group acts transitively on its edges.

Examples and properties
The Gray graph is edge-transitive and regular, but not vertex-transitive.

Edge-transitive graphs include any complete bipartite graph , and any symmetric graph, such as the vertices and edges of the cube.[1] Symmetric graphs are also vertex-transitive (if they are connected), but in general edge-transitive graphs need not be vertex-transitive. The Gray graph is an example of a graph which is edge-transitive but not vertex-transitive. All such graphs are bipartite,[1] and hence can be colored with only two colors.

An edge-transitive graph that is also regular, but not vertex-transitive, is called semi-symmetric. The Gray graph again provides an example. Every edge-transitive graph that is not vertex-transitive must be bipartite and either semi-symmetric or biregular.[2]

The vertex connectivity of an edge-transitive graph always equals its minimum degree.[3]

Marston Conder has compiled a Complete list of all connected edge-transitive graphs on up to 47 vertices and a Complete list of all connected edge-transitive bipartite graphs on up to 63 vertices.

See also
  • Edge-transitive (in geometry)

References
  1. Biggs, Norman (1993). Algebraic Graph Theory (2nd ed.). Cambridge: Cambridge University Press. p. 118. ISBN 0-521-45897-8.
  2. Lauri, Josef; Scapellato, Raffaele (2003), Topics in Graph Automorphisms and Reconstruction, London Mathematical Society Student Texts, Cambridge University Press, pp. 20–21, ISBN 9780521529037.
  3. Watkins, Mark E. (1970), "Connectivity of transitive graphs", Journal of Combinatorial Theory, 8: 23–29, doi:10.1016/S0021-9800(70)80005-9, MR 0266804
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.