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]

This article is about graph theory. For edge transitivity in geometry, see Edge-transitive.
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. Examples of edge but not vertex transitive graphs include the star graphs and complete bipartite graphs where m ≠ n .

An edge-transitive graph that is also regular, but still not vertex-transitive, is called 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.

Every edge-transitive graph that is not vertex-transitive must be bipartite,[1] (and hence can be colored with only two colors), and either semi-symmetric or biregular.[2]

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

See also

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.