Moore graph

one way

Moore graphs

It is easy to see that if a graph $G$ has diameter $d$ (and has any cyclesat all), its girth $g$ can be no more than $2d+1$. For suppose $g⩾2d+2$ and$O$ is a cycle of that minimum length $g$. Take two vertices (nodes) A and Bon $O$ that are $d+1$ steps apart along $O$, one way round; they are $g-(d+1)⩾d+1$ steps apart the other way round. Now either there is no shorterroute between A and B (contradicting diameter $d$) or there is a shorter routeof length creating a cycle of length (contradicting girth $g$).

Definition: A Moore graph is a connected graph withmaximal girth $2d+1$ for its diameter $d$.

It can be shown that Moore graphs are regular, i.e. all vertices have thesame valency. So a Moore graph is characterised by its diameter and valency.

Moore graphs with $d=1$, $g=3$

Diameter 1 means every vertex (node) is adjacent to every other, that is, acomplete graph. Indeed, complete graphs $K_n$ that have cycles ($n⩾3$) havetriangles, so the girth is 3 and they are Moore graphs. Every valency $v⩾2$occurs ($K_n$ has valency $n-1$).

Moore graphs with $d=2$, $g=5$

This is the most interesting case. And http://planetmath.org/node/6948the proof that every vertex has the same valency, $v$ say, and that the graph now has $n=v^2+1$ vertices in all, is easy here.

With some more work, it can be shown there are only 4 possible values for $v$and $n$:

The first three cases each have a unique solution. The existence or otherwise ofthe last case is still http://planetmath.org/node/6331open. It has been shown that if it exists it has, unlike the first three, very little symmetry.

The Hoffman–Singleton graph is a bit hard to draw. Here’s a unifieddescription of the three known Moore graphs of $d=2$, all indices (mod 5):

• Pentagon: five vertices, which we can label $P_k$.

  Each $P_k$ is connected by two edgesto $P_{k\pm 1}$.

• Petersen: ten vertices, which we can label$P_k^{\circ }$ and $P_k^{\star }$.

  Each $P_k^{\circ }$ is connected by two edges to $P_{k\pm 1}^{\circ }$and by one to $P_{2k}^{\star }$.

  Each $P_k^{\star }$ is connected by two edges to $P_{k\pm 1}^{\star }$and by one to $P_{3k}^{\circ }$.

• Hoffman–Singleton: fifty vertices, which we can label$P_{n,k}^{\circ }$ and $P_{m,k}^{\star }$.

  Each $P_{n,k}^{\circ }$ is connected by two edgesto $P_{n,k\pm 1}^{\circ }$and by five to $P_{m,mn+2k}^{\star }$ for all $m$.

  Each $P_{m,k}^{\star }$ is connected by two edgesto $P_{m,k\pm 1}^{\star }$and by five to $P_{n,2mn+3k}^{\circ }$ for all $n$.

The automorphism group of the pentagon is the dihedral group with 10 elements. The one of the Petersen graph is isomorphic to $S_5$, with 120 elements. And the one of the HS graph is isomorphic to $\text{PSU}(3,5)\cdot 2$, with 252 000 elements, a maximal subgroup of another HS, the Higman-Sims group.

Moore graphs with $d⩾3$, $g⩾7$

In these cases, there are only Moore graphs with valency 2, graphsconsisting of a single $2d+1$-gon cycle. This was proven independently byBannai and Ito and by Damerell.