I am looking into the last open question regarding the existence of Moore Graphs of diameter 2. A problem that has been open in combinatorics for more than 55 years.

You may recall that Hoffman and Singleton proved that the only Moore Graphs [: regular graphs achieving the Moore Bound for a given diameter $d$ and a degree $\Delta$] that exist for diameter $d=2$ are for degree $\Delta=2,3,7$ and possibly 57, but for no other degrees.

Little is really known about the 57-Moore Graph. I will attempt to make a complete list of all facts known about it here and hopefully start a conversation or discover more of them that I may have missed.

The 57-Moore Graph will have:

  • Diameter $d=2$, [definition]
  • Degree $\Delta=57$, [definition]
  • Girth $g=5$, [MS10]
  • Number of vertices $|V| = 3250$, [definition]
  • Number of edges $|E| = 92625$, [definition]
  • At most 375 automorphisms, [MS10]
  • Independent Number at most 400, and [reference missing, take it with a grain of salt]
  • It will be regular, [definition]
  • It will not be vertex-transitive. [Ca83]

Some more results from combinations of the above:

  • Proposition 1. [MS10] It's Adjacency Matrix $A$ will satisfy $$A^2 +A - 56I = J,$$ where $I$ is the identity matrix and $J$ the all one matrix. Consequently, it's eigenvalues will be 57, 7, and −8, with multiplicities 1, 1729, and 1520, respectively.

This, to the best of my knowledge, is all we know about the existence of this graph. Have I missed something? Is there something more that we can say about this graph?

Moreover, assuming that this graph exists, is there any hope in pruning down the search space enough to at least try to find it with a semi-brute force approach using supercomputers? Clearly, the search space is too large to brute force even if knew the exact edge count. But can we make other observations towards this or do you think that it is hopeless and that the existence (or not) of this graph would have to be proved some other way?

Thank you.

[Ca83] P.J. Cameron, Automorphism groups of graphs, Selected Topics in Graph Theory II (ed. L. W. Beineke and R. J. Wilson), 89-127, Academic Press, London, 1983.

[MS10] M. Mačaj, J. Širáň, Search for properties of the missing Moore graph, Linear Algebra and its Applications, Volume 432, Issue 9, 15 April 2010, Pages 2381-2398, ISSN 0024-3795 (http://www.sciencedirect.com/science/article/pii/S0024379509003735#)



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.