Enumerating Two-Orbit Graphs

Enumeration of Two-Orbit Graphs: A Group-Theoretic Approach

Overview and Motivation

This work addresses the enumeration of finite, connected graphs whose automorphism group induces exactly two orbits on the vertex set. Two-orbit graphs, as a natural generalization of vertex-transitive (one-orbit) graphs, offer a richer and markedly more numerous class of highly symmetric combinatorial objects. The exponential complexity of the general graph isomorphism problem renders direct brute-force enumeration infeasible for all but the smallest cases. The authors circumvent this combinatorial explosion through a sophisticated algorithmic pipeline grounded in permutation group theory, in particular leveraging Goursat’s Lemma for subdirect products.

The paper provides, for the first time, complete enumerations of connected two-orbit graphs up to 27 vertices, amounting to over ten million isomorphism classes—a significant extension of previous records.

Alternative Methods and Limitations

The authors first consider naïve enumeration: generate all non-isomorphic graphs (e.g., via nauty) and straightforwardly filter to detect two-orbit cases. Due to the super-exponential growth of the number of graphs as a function of $n$, this approach fails for $n > 11$.

An improved, constraint-based strategy using the SMS SAT-modulo-symmetry framework can encode orbit sizes, degree constraints, and local triangle counts, scaling up to $n = 16$ with major computational resources. Nevertheless, these methods are fundamentally bottlenecked by the vast search space; a fundamentally different approach is required for larger values of $n$.

Group-Theoretic Generation Pipeline

The central insight is to invert the enumeration process. Rather than generating graphs and testing their automorphism groups, the method starts from permutation groups with the requisite two-orbit action and systematically constructs all graphs invariant under these groups, which are then deduplicated up to isomorphism.

A key observation is that, for a graph $G$ and subgroup $H < \operatorname{Aut}(G)$, the group $H$ partitions the unordered pairs of vertices into edge orbits. All graphs invariant under $H$ are obtained by taking subsets of these edge orbits.

Necessarily, for two-orbit graphs, attention is restricted to permutation groups acting with precisely two orbits on $V(G)$ and no proper subgroup acting transitively on both orbits (minimal two-orbit groups). The enumeration problem thus becomes one of generating all such minimal groups up to degree $n$, and then all graphs invariant under their action.

Subdirect Products and Goursat’s Lemma

The enumeration of relevant permutation groups is fundamentally a problem in the construction of two-orbit subdirect products. If $n > 11$0, with nontrivial partition sizes, the two-orbit automorphism group $n > 11$1 must be a subdirect product of transitive groups $n > 11$2 and $n > 11$3, projecting surjectively on both factors.

Goursat’s Lemma provides a full characterization: each subdirect product corresponds to $n > 11$4 where $n > 11$5, $n > 11$6 are normal subgroups, and $n > 11$7 is an isomorphism between the quotients. This construction efficiently parameterizes all possible two-orbit subdirect products and thereby all possible candidate automorphism groups of two-orbit graphs.

Pruning and Optimization

Given the rapid growth in candidate group count, the pipeline integrates aggressive pruning strategies:

• Essential Kernel Pruning: Kernels $n > 11$8 (or $n > 11$9) that do not satisfy an “essentiality” criterion guarantee non-minimality of the resulting subdirect product and can be discarded without further computation. Over 90% of kernel pairs for $n = 16$0 are eliminated this way.
• Minimality Testing: For $n = 16$1 of order $n = 16$2, no proper subgroup can act transitively on both orbits, which is exploited for a fast check. Otherwise, subgroups are explicitly tested for the desired orbit action and order.
• Diagonal Groups: When both projection kernels are trivial, corresponding diagonal groups can often be excluded by the existence of smaller transitive subgroups, unless acting on degrees $n = 16$3 or $n = 16$4.
• Deduplication at Orbital Level: Rather than deduplicating graphs post-generation, groups are deduplicated via their orbital configuration prior to graph generation in two rounds, significantly reducing computational effort.

Numerical Results

The group-theoretic pipeline enables generation and validation of all connected two-orbit graphs up to 27 vertices, which totals 10,094,721 isomorphism classes. For smaller $n = 16$5, results match and extend partial enumerations available in the literature. The counts for higher $n = 16$6 dramatically surpass previous enumerations, e.g., for $n = 16$7, there are over 1.85 million connected two-orbit graphs.

Implications, Limitations, and Future Directions

This enumeration fills a major gap analogous to the established catalogues of vertex-transitive graphs. It produces a large resource for further studies in structural graph theory, extremal combinatorics, and the theory of permutation groups. The framework demonstrates the critical advantage of incorporating group actions and algebraic structure into combinatorial object enumeration at scale.

Potential improvements include more aggressive isomorph rejection during graph generation, the use of edge-coloring isomorphisms in search tree pruning, and automated certificate generation for non-minimality to reduce group-theoretic computations. The method could be extended to $n = 16$8-orbit graphs for fixed $n = 16$9 via analogous group-theoretic constructions, though at increased computational cost.

Conclusion

This paper introduces and implements an optimized, group-theory-driven algorithm that enables complete enumeration of connected two-orbit graphs up to 27 vertices, an achievement unattainable by prior direct or constraint-based methods. The integration of Goursat’s Lemma, essential kernel pruning, and orbital-level deduplication is central to this scalability. The resulting datasets open new opportunities for research in highly symmetric but non-transitive graph classes and suggest further algorithmic advances for broader classes of combinatorial structures.

Reference: "Enumerating Two-Orbit Graphs" (2604.00898)