Abstract
A graph is said to be edge-transitive if its automorphism group acts transitively on its edges. It is known that edge-transitive graphs are either vertex-transitive or bipartite. In this paper we present a complete classification of all connected edge-transitive graphs on less than or equal to $20$ vertices. We then present a construction for an infinite family of edge-transitive bipartite graphs, and use this construction to show that there exists a non-trivial bipartite subgraph of $K_{m,n}$ that is connected and edge-transitive whenever $gcd(m,n)>2$. Additionally, we investigate necessary and sufficient conditions for edge transitivity of connected $(r,2)$ biregular subgraphs of $K_{m,n}$, as well as for uniqueness, and use these results to address the case of $gcd(m,n)=2$. We then present infinite families of edge-transitive graphs among vertex-transitive graphs, including several classes of circulant graphs. In particular, we present necessary conditions and sufficient conditions for edge-transitivity of certain circulant graphs.
Introduction
In the study of graph symmetry, edge-transitivity represents a high degree of structural uniformity. A graph $G$ is defined as edge-transitive if, for any two edges $e_1$ and $e_2$ in $G$, there exists an automorphism $\phi \in Aut(G)$ such that $\phi(e_1) = e_2$. Essentially, every edge in the graph is indistinguishable from any other under the graph's own symmetry operations.
A fundamental result in algebraic graph theory states that any connected edge-transitive graph must fall into one of two categories: it is either vertex-transitive (where all vertices are equivalent) or it is bipartite. While many symmetric graphs, such as the Platonic solids or complete graphs, are well-documented, this research provides a systematic census of small edge-transitive graphs and establishes new theoretical frameworks for constructing infinite families of these structures.
Classification of Small Edge-Transitive Graphs
One of the primary contributions of this work is the exhaustive classification of all connected edge-transitive graphs with $n \le 20$ vertices. Utilizing Brendan McKay’s comprehensive graph databases, the authors filtered and identified every graph meeting the edge-transitivity criteria.
The results of this census were contributed to the Online Encyclopedia of Integer Sequences (OEIS) under sequence #A095424. The classification reveals the increasing complexity of symmetric structures as vertex count grows; for instance, while there are only a handful of such graphs for small $n$, the count rises to 19 graphs for $n=12$ and 43 graphs for $n=20$.
To facilitate this classification, the authors leveraged the relationship between a graph $G$ and its line graph $L(G)$. A graph $G$ is edge-transitive if and only if its line graph $L(G)$ is vertex-transitive. This duality allows researchers to apply the more mature tools of vertex-transitivity analysis to the problem of edge-transitivity.
Bipartite Subgraphs and the $gcd(m, n)$ Threshold
The paper investigates the existence of edge-transitive subgraphs within the complete bipartite graph $K_{m,n}$. A significant finding is the role of the greatest common divisor ($gcd$) of the two vertex set sizes. The authors prove that a non-trivial, connected, edge-transitive subgraph of $K_{m,n}$ is guaranteed to exist whenever $gcd(m,n) > 2$.
Furthermore, the research examines $(r, 2)$ biregular subgraphs—graphs where vertices in one partition have degree $r$ and vertices in the other have degree 2. The authors establish that:
- If $mr = 2n$ and $r$ is even, there always exists an edge-transitive $(r, 2)$ biregular subgraph of $K_{m,n}$.
- Edge-transitivity in these cases requires a "uniform partitioning" of edges, meaning the distribution of edges across neighborhoods must be perfectly balanced to maintain symmetry.
Edge-Transitivity in Circulant Graphs
Circulant graphs, where vertices are arranged in a cyclic order and edges are defined by a set of "jumps" or chords, provide a rich field for studying vertex-transitivity. However, determining which circulants are also edge-transitive is more complex.
The authors identify four specific infinite classes of "3-circulant" graphs (those with three distinct chord lengths) that are guaranteed to be edge-transitive. A key theoretical result, Theorem 3.7, establishes a group-theoretic condition for this property: if the set of chord lengths in a circulant graph forms a group under multiplication modulo $n$, the resulting graph is edge-transitive. This provides a clear algebraic recipe for generating highly symmetric circulant structures.
Conclusion and Future Directions
While this work provides a complete census up to $n=20$, the computational complexity of identifying isomorphisms grows exponentially with the number of vertices and chords. Recent work by other researchers, such as Conder and Verret, has extended these lists up to 63 vertices using the Magma algebra system, highlighting the ongoing effort to map the landscape of symmetric graphs.
Two open conjectures (3.1 and 3.2) remain regarding the necessary conditions for edge-transitivity in general circulant graphs. Future research may focus on resolving these conjectures and developing a more unified naming convention for the various "unnamed" symmetric graphs identified in recent censuses.
Summary updated