Moore graph

In graph theory, a Moore graph is a regular graph of degree d and diameter k whose number of vertices equals the upper bound




1
+
d

∑

i
=
0


k
−
1


(
d
−
1

)

i


.


{\displaystyle 1+d\sum _{i=0}^{k-1}(d-1)^{i}.}
An equivalent definition of a Moore graph is that it is a graph of diameter



k


{\displaystyle k}
with girth



2
k
+
1


{\displaystyle 2k+1}
. Another equivalent definition of a Moore graph



G


{\displaystyle G}
is that it has girth



g
=
2
k
+
1


{\displaystyle g=2k+1}
and precisely





n
g


(
m
−
n
+
1
)


{\displaystyle {\frac {n}{g}}(m-n+1)}
cycles of length



g


{\displaystyle g}
, where



n


{\displaystyle n}
and



m


{\displaystyle m}
are, respectively, the numbers of vertices and edges of



G


{\displaystyle G}
. They are in fact extremal with respect to the number of cycles whose length is the girth of the graph.Moore graphs were named by Hoffman & Singleton (1960) after Edward F. Moore, who posed the question of describing and classifying these graphs.
As well as having the maximum possible number of vertices for a given combination of degree and diameter,
Moore graphs have the minimum possible number of vertices for a regular graph with given degree and girth. That is, any Moore graph is a cage. The formula for the number of vertices in a Moore graph can be generalized to allow a definition of Moore graphs with even girth as well as odd girth, and again these graphs are cages.

Created with WikipediaReaderReborn (c) WikipediaReader