Abstract
A graph is defined as edge-transitive if its automorphism group acts transitively on its edges. Such graphs are fundamentally either vertex-transitive or bipartite. This paper presents a complete classification of connected edge-transitive graphs with up to 20 vertices. We further investigate biregular bipartite edge-transitive graphs, establishing deep connections to combinatorial designs, and demonstrate that the complements of Cartesian products of complete graphs form a distinct family of edge-transitive graphs.
Introduction
In the study of graph theory, symmetry serves as a primary lens for understanding structural properties. A graph is edge-transitive if every edge is equivalent under the graph’s automorphisms—meaning any edge can be mapped to any other edge while preserving the overall structure.
While vertex-transitive graphs (where all vertices are symmetric) are well-documented, edge-transitive graphs present a more complex landscape. Crucially, an edge-transitive graph is not necessarily vertex-transitive; it may instead be bipartite, with two distinct sets of vertices exhibiting different properties. This research aims to classify small-scale edge-transitive graphs, understand the conditions for edge-transitivity in biregular bipartite graphs, and bridge the theoretical gap between graph theory and combinatorial designs.
Methodology
The classification and analysis were conducted through a combination of computational search and formal mathematical proof.
Exhaustive Classification
The researchers utilized Brendan McKay’s graph databases to identify and categorize all connected edge-transitive graphs with 20 or fewer vertices. This foundational work allowed for the identification of patterns and the verification of theoretical predictions.
Inductive Construction and Cloning
A key methodological contribution is the "cloning" lemma (Lemma 12). This allows for the extension of a small edge-transitive bipartite graph into a larger one by systematically duplicating vertices while maintaining the required symmetries.
Design Mapping and Graph Operations
The study analyzed Balanced Incomplete Block Designs (BIBDs). By treating the "objects" of a design as one vertex set and the "blocks" as another, the authors created incidence graphs. These were then tested for edge-transitivity using computational tools like Mathematica. Additionally, the researchers employed Cartesian product and line graph operations to prove the existence of new symmetric families.
Key Insights
The Bipartite/Vertex-Transitive Split
A fundamental property (Proposition 2) dictates that an edge-transitive graph must be either vertex-transitive or bipartite. In the bipartite case, the graph is "biregular," meaning all vertices in one partition have degree $r$ and all in the other have degree $s$.
Symmetry and Combinatorial Designs
A significant finding is that while many BIBDs appear symmetric, they do not inherently yield edge-transitive graphs. The edge-transitivity depends heavily on the construction method of the design (e.g., those derived from linear transformations).
Arc-Transitivity
For graphs where one partition has a degree of 2, the authors proved that edge-transitivity is equivalent to the graph being derived from an arc-transitive multigraph (where the direction of the edge is also symmetric).
Key Results
- Full Catalog: A complete classification of connected edge-transitive graphs for $|V| \leq 20$ was established and contributed to the Online Encyclopedia of Integer Sequences (OEIS #A095424).
- Existence Theorems: Theorem 13 proves that if the greatest common divisor of the sizes of the two bipartite sets is greater than 2 ($gcd(m, n) > 2$), a non-complete, connected, edge-transitive subgraph always exists.
- Biregular Links: Theorem 15 establishes a definitive link between $(r, 2)$-biregular edge-transitive graphs and arc-transitive graphs.
- New Families: Theorem 22 formally proves that the complement of the Cartesian product of two complete graphs ($\overline{K_m \times K_n}$) is edge-transitive, providing a robust tool for generating highly symmetric networks.
Conclusion and Future Work
While this paper provides a comprehensive classification for small graphs, several challenges remain. The construction method for bipartite subgraphs currently fails when $gcd(m, n) = 2$, marking a clear area for future refinement. Furthermore, extending the exploration of $(r, k)$-biregular graphs for $k > 2$ remains a significant open problem. Finally, distinguishing between non-isomorphic designs that lead to identical graph properties requires further investigation to fully map the intersection of these two mathematical fields.
Summary updated