Moore graph (original) (raw)

\PMlinkescapephrase

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 2⁢d+1. For suppose g⩾2⁢d+2 andO 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 r<d+1 creating a cycle of length d+1+r<2⁢d+2(contradicting girth g).

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, acomplete graph. Indeed, complete graphs Kn that have cycles (n⩾3) havetriangles, so the girth is 3 and they are Moore graphs. Every valency v⩾2occurs (Kn 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=v2+1 vertices in all, is easy here.

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

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 Pk.
  Each Pk is connected by two edges to Pk±1.
• •
  Petersen: ten vertices, which we can labelPk∘ and Pk⋆.
  Each Pk∘ is connected by two edges to Pk±1∘and by one to P2⁢k⋆.
  Each Pk⋆ is connected by two edges to Pk±1⋆and by one to P3⁢k∘.
• •
  Hoffman–Singleton: fifty vertices, which we can labelPn,k∘ and Pm,k⋆.
  Each Pn,k∘ is connected by two edges to Pn,k±1∘and by five to Pm,m⁢n+2⁢k⋆ for all m.
  Each Pm,k⋆ is connected by two edges to Pm,k±1⋆and by five to Pn,2⁢m⁢n+3⁢k∘ 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 S5, with 120 elements. And the one of the HS graph is isomorphic to PSU⁢(3,5)⋅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 2⁢d+1-gon cycle. This was proven independently by Bannai and Ito and by Damerell.