Edge-transitive graph

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 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]

In other words, a graph is edge-transitive if its automorphism group acts transitively upon 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]

See also

References

  1. 1 2 3 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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.