[seqfan] Re: A064513, A058201, and the graph degree/diameter problem.

Chris Thompson cet1 at cam.ac.uk
Wed Nov 18 16:12:26 CET 2015


On Nov 17 2015, Neil Sloane wrote:

>Allan, Chris,
>Thanks for those comments.
>I "deaded" A058201, and I'm revising A064513.
>
>My old notes there say that it is known that a(7)=50. Do you believe that?

That has been known since the first construction of the Hoffman-Singleton
graph: probably http://dx.doi.org/10.1147/rd.45.0497

The Moore upper bound, a(n) <= n^2 + 1 in this case, can be achieved with
equality only for n = 2, 3, 7 or 57. The first three cases give unique
graphs (5-cycle, Petersen graph, Hoffman-Singleton graph) while the existence
or otherwise of a Moore graph with degree 57 is a notorious open problem.

Apart from the Wikipedia page that Allan mentioned, there is one for
the Hoffman-Singleton graph

  https://en.wikipedia.org/wiki/Hoffman%E2%80%93Singleton_graph

with plenty more references.

-- 
Chris Thompson
Email: cet1 at cam.ac.uk



More information about the SeqFan mailing list