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⩾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)⩾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 creating a cycle of length (contradicting girth $g$).

Definition: A Moore graph 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⩾3$) have triangles, 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$:

$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_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 edges to $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 edges to $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, graphs consisting of a single $2d+1$-gon cycle. This was proven independently by Bannai and Ito and by Damerell.

Title	Moore graph
Canonical name	MooreGraph
Date of creation	2013-03-22 15:11:27
Last modified on	2013-03-22 15:11:27
Owner	Mathprof (13753)
Last modified by	Mathprof (13753)
Numerical id	10
Author	Mathprof (13753)
Entry type	Definition
Classification	msc 05C75