Abstract
This study reports a new milestone in graph theory: the enumeration of non-isomorphic 4-regular graphs of order 23. By adapting the classical GENREG algorithm for massive parallel execution on international supercomputers, we expanded the OEIS sequence A006820, identifying exactly 429,668,180,677,439 graphs. Beyond the counting record, our search identified several optimal regular graphs with minimum diameters, offering potential improvements for interconnection network topologies in high-performance computing.
Introduction
In graph theory, enumeration involves listing all possible graphs meeting specific criteria—such as being "regular" (where every vertex has the same degree $k$)—without redundant counting of isomorphic structures. While seemingly abstract, regular graphs are foundational to computer architecture. The interconnection networks of supercomputers are essentially large regular graphs; finding topologies with the smallest Average Shortest Path Length (ASPL) is critical for reducing communication latency.
However, the "combinatorial explosion" makes this task exponentially difficult as the number of vertices (order $n$) grows. The previous record for 4-regular graphs (quartics) had remained at $n=22$ since 2011. This work breaks that eight-year-old barrier.
Methodology: Scaling GENREG for Supercomputers
The researchers utilized GENREG, a well-established serial generator for regular graphs, and re-engineered it for distributed-memory environments using the Message Passing Interface (MPI).
Dynamic Task Scheduling
Graph generation is inherently unbalanced; different branches of the search tree vary wildly in computational depth. To address this, the team implemented a master-worker framework. A master node adaptively dispatches sub-tasks—decomposed into 50,000 to 200,000 units for order 23—to a pool of workers, ensuring high CPU utilization across thousands of cores.
Multi-Cluster Execution
The computation was distributed across three distinct supercomputing clusters:
- SeaWulf (Stony Brook University, USA)
- Tianhe-1 (National Supercomputer Center in Tianjin, China)
- IBM Quinde (Escuela Politécnica Nacional, Ecuador)
This "opportunistic" approach leveraged fragmented resources across international borders, totaling nearly 100 core-years of computation.
Results and Discussion
The primary achievement is the expansion of the OEIS sequence A006820. The exact number of connected 4-regular graphs of order 23 was determined to be 429,668,180,677,439.
Performance Insights
The study revealed significant performance variations between hardware architectures. Intel Xeon Gold processors in the SeaWulf cluster achieved a core speed of 178,000 graphs per second, nearly triple the 56,000 graphs per second observed on IBM Power8 cores. Scalability tests showed the framework could effectively utilize up to 3,000 cores before the single master node became a communication bottleneck.
Discovery of Optimal Topologies
Beyond the raw count, the search identified 56 specific 3-regular graphs of order 32 with absolute minimum ASPL. These "optimal" graphs provide superior network efficiency compared to standard topologies used in contemporary Beowulf clusters.
Conclusion
By successfully enumerating 4-regular graphs of order 23, this research demonstrates the power of adapting classical algorithms for modern parallel architectures. The discovery of new optimal topologies provides a practical path forward for designing lower-latency interconnection networks. Future work will focus on multi-level scheduling to overcome current master-node bottlenecks, potentially pushing the frontier to order 24 and beyond.
Summary updated