Edge-transitive graphs and combinatorial designs

Heather Newman, Héctor Miranda, Adam Gregory, Darren A. Narayan

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.

Sequence of bipartite graphs illustrating inductive construction methods.

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

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. We present a complete classification of all connected edge-transitive graphs on less than or equal to [math] vertices. We investigate biregular bipartite edge-transitive graphs and present connections to combinatorial designs, and we show that the Cartesian products of complements of complete graphs give an additional family of edge-transitive graphs.
BibTeX
@inproceedings{newman2019edge,
  author = {Heather Newman and Héctor Miranda and Adam Gregory and Darren A. Narayan},
  title = {{Edge-transitive graphs and combinatorial designs}},
  booktitle = {Involve},
  year = {2019},
  doi = {10.2140/involve.2019.12.1329},
}
Figure