# Moore graph

one way

## Moore graphs

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

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

It can be shown that Moore graphs are regular, i.e. all vertices have the same 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, a complete graph. Indeed, complete graphs $K_{n}$ that have cycles ($n\geqslant 3$) have triangles, so the girth is 3 and they are Moore graphs. Every valency $v\geqslant 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$:

$v$ $n$ graph
2 5 pentagon
3 10 Petersen graph
7 50 Hoffman–Singleton graph
57 3250            ???

The first three cases each have a unique solution. The existence or otherwise of the 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 unified description 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 edges to $P_{k\pm 1}$.

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

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

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

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

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

Each $P^{\,\star}_{m,k}$ is connected by two edges to $P^{\,\star}_{m,k\pm 1}$ and by five to $P^{\,\circ}_{n,2mn+3k}$ 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 $\hbox{PSU}(3,5)\cdot 2$, with 252 000 elements, a maximal subgroup of another HS, the Higman-Sims group.

## Moore graphs with $d\geqslant 3$, $g\geqslant 7$

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

Title Moore graph MooreGraph 2013-03-22 15:11:27 2013-03-22 15:11:27 Mathprof (13753) Mathprof (13753) 10 Mathprof (13753) Definition msc 05C75