Potential Subgraphs of the Missing Moore Graph
Open Access
Abstract
The possible existence of a Moore graph of diameter 2 and degree 57 has been an open question for more than six decades. In this paper, certain subgraphs of this graph, referred to as t-subgraphs, are considered. Exploiting symmetry by assuming a cyclic group of permutations representing edges joining leaf nodes of branches of a tree, a tractable constraint model for t-subgraphs is created. This can be solved using the Google OR Tools CP-SAT solver. Larger potential t-subgraphs than those currently known are constructed. This further extends a construction of certain sets of mutually orthogonal Latin rectangles. The implications for non-existence proofs of the Moore graph are considered.Keywords
This publication has 11 references indexed in Scilit:
- The missing Moore graph as an optimization problemEURO Journal on Computational Optimization, 2023
- A survey on the missing Moore graphLinear Algebra and its Applications, 2019
- Moore Graphs and Beyond: A survey of the Degree/Diameter ProblemThe Electronic Journal of Combinatorics, 2013
- Search for properties of the missing Moore graphLinear Algebra and its Applications, 2010
- Handbook of Combinatorial Designs2006
- Automorphisms of Aschbacher GraphsAlgebra and Logic, 2001
- Algebraic Graph Theory1974
- The nonexistence of rank three permutation groups of degree 3250 and subdegree 57Journal of Algebra, 1971
- On Trivalent GraphsBulletin of the London Mathematical Society, 1971
- On Moore Graphs with Diameters 2 and 3IBM Journal of Research and Development, 1960