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
Edge-transitive graph
The Gray graph is edge-transitive and regular, but not vertex-transitive.
Edge-transitive graphs include any complete bipartite graph \( K_{m,n} \), 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
Biggs, Norman (1993). Algebraic Graph Theory (2nd ed.). Cambridge: Cambridge University Press. p. 118. ISBN 0-521-45897-8.
Lauri, Josef; Scapellato, Raffaele (2003), Topics in Graph Automorphisms and Reconstruction, London Mathematical Society Student Texts, Cambridge University Press, pp. 20–21, ISBN 9780521529037.
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
External links
Weisstein, Eric W. "Edge-transitive graph". MathWorld.
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
