A New Record of Graph Enumeration Enabled by Parallel Processing

• DOI: 10.3390/math7121214
• Publication Date: 2019-12-10T15:52:41Z
• Authors: Zhipeng Xu; Xiaolong Huang; Fabian Jimenez; Yuefan Deng
• Keywords: FOS: Computer and information sciences; Discrete Mathematics (cs.DM); parallel computing; 05C30, 68R10; 02 engineering and technology; dynamical scheduling; regular graph; FOS: Mathematics; 0202 electrical engineering, electronic engineering, information engineering; Mathematics - Combinatorics; Combinatorics (math.CO); Computer Science - Discrete Mathematics

Using three supercomputers, we broke a record set in 2011, in the enumeration of non-isomorphic regular graphs by expanding the sequence of A006820 in the Online Encyclopedia of Integer Sequences (OEIS), to achieve the number for 4-regular graphs of order 23 as 429,668,180,677,439, while discovering several regular graphs with minimum average shortest path lengths (ASPL) that can be used as interconnection networks for parallel computers. The enumeration of 4-regular graphs and the discovery of minimal-ASPL graphs are extremely time consuming. We accomplish them by adapting GENREG, a classical regular graph generator, to three supercomputers with thousands of processor cores.