PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (194)
Orphanage
Unclass'd
Unproven (498)
Corrections (25)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
Moore graph (Definition)

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\ge2d+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) \ge 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\ge3$) have triangles, so the girth is 3 and they are Moore graphs. Every valency $v\ge2$ occurs ($K_n$ has valency $n-1$).

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^{\vphantom0}_k$.

    Each $P^{\vphantom0}_k$ is connected by two edges to $P^{\vphantom0}_{k\pm1}$.

  • 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\pm1}$ and by one to $P^{\,\star}_{2k}$.

    Each $P^{\,\star}_k$ is connected by two edges to $P^{\,\star}_{k\pm1}$ 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\pm1}$ 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\pm1}$ 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 252000 elements, a maximal subgroup of another HS, the Higman-Sims group.

Moore graphs with $d\ge3$, $g\ge7$

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.



"Moore graph" is owned by Mathprof. [ full author list (2) | owner history (1) ]
(view preamble)

View style:


Attachments:
Moore graphs of $d=2$ are $v$-valent and order is $v^2+1$ (Proof) by marijke
Log in to rate this entry.
(view current ratings)

Cross-references: group, maximal subgroup, isomorphic, dihedral group, automorphism group, edges, label, indices, symmetry, solution, Petersen graph, pentagon, triangles, complete graph, adjacent, vertex, valency, regular, connected graph, vertices, girth, cycles, diameter, graph, easy to see
There are 2 references to this entry.

This is version 7 of Moore graph, born on 2005-04-11, modified 2006-09-13.
Object id is 6947, canonical name is MooreGraph.
Accessed 2231 times total.

Classification:
AMS MSC: 05C75 (Combinatorics :: Graph theory :: Structural characterization of types of graphs)
Pending Errata and Addenda
None.
[ View all 2 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)