For fixed integers $latex r > 0$, and odd $latex g$, a Moore graph is an $latex r$-regular graph of girth $latex g$ which has the minimum number of vertices $latex n$ among all such graphs with the same regularity and girth.
(Recall, A the girth of a graph is the length of its shortest cycle, and it’s regular if all its vertices have the same degree)
Problem (Hoffman-Singleton): Find a useful constraint on the relationship between $latex n$ and $latex r$ for Moore graphs of girth $latex 5$ and degree $latex r$.
Note: Excluding trivial Moore graphs with girth $latex g=3$ and degree $latex r=2$, there are only two known Moore graphs: (a) the Petersen graph and (b) this crazy graph:
The solution to the problem shows that there are only a few cases left to check.
Solution: It is easy to show that the minimum number of vertices of a…
View original post 761 more words