You are here
HomeMoore graph
Primary tabs
Moore graph
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\lt d+1$ creating a cycle of length $d+1+r\lt 2d+2$ (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\geqslant 3$) have triangles, so the girth is 3 and they are Moore graphs. Every valency $v\geqslant 2$ occurs ($K_{n}$ has valency $n1$).
Moore graphs with $d=2$, $g=5$
This is the most interesting case. And the 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 open. 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}$.

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 HigmanSims 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.
Mathematics Subject Classification
05C75 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections