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.
In other words, a graph is edge-transitive if its automorphism group acts transitively on its edges.
Examples and properties
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 ... (sequence A095424 in the OEIS)
Edge-transitive graphs include all symmetric graphs, such as the vertices and edges of the cube. Symmetric graphs are also vertex-transitive (if they are connected), but in general edge-transitive graphs need not be vertex-transitive. Every connected edge-transitive graph that is not vertex-transitive must be bipartite, (and hence can be colored with only two colors), and either semi-symmetric or biregular.
Examples of edge but not vertex transitive graphs include the complete bipartite graphs where m ≠ n, which includes the star graphs . 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 Km,n 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. So edge transitive subgraphs exist for K3,6, K4,6 and K5,10 but not K4,10. 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.
where m ≠ n, which includes the star graphs 
. 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 Km,n 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. So edge transitive subgraphs exist for K3,6, K4,6 and K5,10 but not K4,10. 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, 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.
The vertex connectivity of an edge-transitive graph always equals its minimum degree.
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.
- Newman, Heather A.; Miranda, Hector; Narayan, Darren A (2019). "Edge-transitive graphs and combinatorial designs". Involve: A Journal of Mathematics. 12 (8): 1329–1341. arXiv:1709.04750. doi:10.2140/involve.2019.12.1329. S2CID 119686233.
- 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