The missing Moore graph as an optimization problem

Abstract

It has been an open question for 6 decades whether a Moore graph of diameter 2 and degree 57 exists. In this paper the question is posed as an optimization problem and an algorithm is described. The algorithm converges to solutions which are massively short of the number of edges required. This, and other supporting work, tend to suggest that the graph does not exist. The formulation presented is a particularly hard testbed for optimization algorithms. It is left as a challenge to others to develop alternative algorithms that may support the claim, or find solutions with more edges, or even construct the Moore graph.

Keywords

• Graph theory
• Moore graphs
• Diameter
• Girth