Moore graph


one way

Moore graphs

It is easy to see that if a graph G has diameterMathworldPlanetmathPlanetmath d (and has any cycles at all), its girth g can be no more than 2d+1. For suppose g2d+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 r<d+1 creating a cycle of length d+1+r<2d+2 (contradicting girth g).

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

It can be shown that Moore graphs are regularPlanetmathPlanetmathPlanetmathPlanetmath, 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 adjacentPlanetmathPlanetmathPlanetmath to every other, that is, a complete graphMathworldPlanetmath. Indeed, complete graphs Kn that have cycles (n3) have triangles, so the girth is 3 and they are Moore graphs. Every valency v2 occurs (Kn has valency n-1).

Moore graphs with d=2, g=5

This is the most interesting case. And 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 v and n:

v n graph
2 5 pentagonMathworldPlanetmath
3 10 Petersen graphMathworldPlanetmathPlanetmath
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 It has been shown that if it exists it has, unlike the first three, very little symmetryMathworldPlanetmathPlanetmath.

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 label Pk and Pk.

    Each Pk is connected by two edges to Pk±1 and by one to P2k.

    Each Pk is connected by two edges to Pk±1 and by one to P3k.

  • Hoffman–Singleton: fifty vertices, which we can label Pn,k and Pm,k.

    Each Pn,k is connected by two edges to Pn,k±1 and by five to Pm,mn+2k for all m.

    Each Pm,k is connected by two edges to Pm,k±1 and by five to Pn,2mn+3k for all n.

The automorphism groupMathworldPlanetmath of the pentagon is the dihedral groupMathworldPlanetmath with 10 elements. The one of the Petersen graph is isomorphicPlanetmathPlanetmathPlanetmathPlanetmath 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 d3, g7

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