-
A Moore graph is a graph with diameter
and girth . -
There are four known Moore graphs
where . : The odd cycles .(see cycles) - The Petersen Graph
- The Huffman Singleton graph.
-
(Godsil 5.8.1) A Moore graph is regular.
-
(Godsil 5.8.2) A Moore graph is distance regular.
- Moore Graphs of diameter greater than
do not exist. - A Moore graph of diameter
must be -regular .
- Moore Graphs of diameter greater than
-
(Godsil 5.9.1) An independent set
in a Moore graph of diameter and degree contains at most vertices. If
then every vertex not in has exactly neighbors in .
Hoffman-Singleton Graph
-
One way to construct the Hoffman Singleton Graph is as follows:
Take
pentagons and pentagrams . Follow the adjacency rule where and . -
Another way is using heptads.
- Choose an
orbit of heptads from . - The vertices of the Huffman Singleton graph are the heptads and the triples.
- A heptad is joined to a triple if and only if it contains the triple.
- A triple is joined to a triple if and only if they are disjoint.
- Choose an
