View source for Moore graph

{{short description|Regular graph with girth more than twice its diameter}}
{{unsolved|mathematics|Does a Moore graph with girth 5 and degree 57 exist?}}

In [[Graph theory|graph theory]], a '''Moore graph''' is a [[Regular graph|regular graph]] whose [[Girth (graph theory)|girth]] (the shortest [[Cycle (graph theory)|cycle]] length) is more than twice its [[Diameter (graph theory)|diameter]] (the distance between the farthest two [[Vertex (graph theory)|vertices]]). If the [[Degree (graph theory)|degree]] of such a graph is {{mvar|d}} and its diameter is {{mvar|k}}, its girth must equal {{math|2''k'' + 1}}. This is true, for a graph of degree {{mvar|d}} and diameter {{mvar|k}}, if and only if its number of vertices equals
:<math>1+d\sum_{i=0}^{k-1}(d-1)^i,</math>
an upper bound on the largest possible number of vertices in any graph with this degree and diameter. Therefore, these graphs solve the [[Degree diameter problem|degree diameter problem]] for their parameters.

Another equivalent definition of a Moore graph {{mvar|G}} is that it has girth {{math|1=''g'' = 2''k'' + 1}} and precisely {{math|{{sfrac|''n''|''g''}}(''m'' – ''n'' + 1)}} cycles of length {{mvar|g}}, where {{mvar|n}} and {{mvar|m}} are, respectively, the numbers of vertices and edges of {{mvar|G}}. They are in fact extremal with respect to the number of cycles whose length is the girth of the graph.{{sfnp|Azarija|Klavžar|2015}}

Moore graphs were named by {{harvtxt|Hoffman|Singleton|1960}} after [[Biography:Edward F. Moore|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 (graph theory)|cage]].{{sfnp|Erdős|Rényi|Sós|1966}} 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.

== Bounding vertices by degree and diameter ==

[[Image:Petersen-as-Moore.svg|thumb|The [[Petersen graph|Petersen graph]] as a Moore graph.  Any breadth first search tree has {{math|''d''(''d'' − 1){{sup|''i''−1}}}} vertices in its {{mvar|i}}-th level for {{math|''i'' &ge; 1}}.]]

Let {{mvar|G}} be any graph with maximum degree {{mvar|d}} and diameter {{mvar|k}}, and consider the tree formed by breadth first search starting from any vertex {{mvar|v}}. This tree has 1 vertex at level 0 ({{mvar|v}} itself), and at most {{mvar|d}} vertices at level 1 (the neighbors of {{mvar|v}}). In the next level, there are at most {{math|''d''(''d'' − 1)}} vertices: each neighbor of {{mvar|v}} uses one of its adjacencies to connect to {{mvar|v}} and so can have at most {{math|''d'' − 1}} neighbors at level 2. In general, a similar argument shows that at any level {{math|1 ≤ ''i'' ≤ ''k''}}, there can be at most {{math|''d''(''d'' − 1){{sup|''i''−1}}}} vertices. Thus, the total number of vertices can be at most
:<math>1+d\sum_{i=0}^{k-1}(d-1)^i.</math>
{{harvtxt|Hoffman|Singleton|1960}} originally defined a Moore graph as a graph for which this bound on the number of vertices is met exactly. Therefore, any Moore graph has the maximum number of vertices possible among all graphs with maximum degree {{mvar|d}} and diameter {{mvar|k}}.

Later, {{harvtxt|Singleton|1968}} showed that Moore graphs can equivalently be defined as having diameter {{mvar|k}} and girth {{math|2''k'' + 1}}; these two requirements combine to force the graph to be {{mvar|d}}-regular for some {{mvar|d}} and to satisfy the vertex-counting formula.

== Moore graphs as cages ==

Instead of upper bounding the number of vertices in a graph in terms of its maximum degree and its diameter, we can calculate via similar methods a lower bound on the number of vertices in terms of its minimum degree and its [[Girth (graph theory)|girth]].{{sfnp|Erdős|Rényi|Sós|1966}} Suppose {{mvar|G}} has minimum degree {{mvar|d}} and girth {{math|2''k'' + 1}}.  Choose arbitrarily a starting vertex {{mvar|v}}, and as before consider the breadth-first search tree rooted at {{mvar|v}}. This tree must have one vertex at level 0 ({{mvar|v}} itself), and at least {{mvar|d}} vertices at level 1. At level 2 (for {{math|''k'' > 1}}), there must be at least {{math|''d''(''d'' − 1)}} vertices, because each vertex at level 1 has at least {{math|''d'' − 1}} remaining adjacencies to fill, and no two vertices at level 1 can be adjacent to each other or to a shared vertex at level 2 because that would create a cycle shorter than the assumed girth.  In general, a similar argument shows that at any level {{math|1 ≤ ''i'' ≤ ''k''}}, there must be at least {{math|''d''(''d'' − 1){{sup|''i''}}}} vertices. Thus, the total number of vertices must be at least
:<math>1+d\sum_{i=1}^{k-1}(d-1)^i.</math>
In a Moore graph, this bound on the number of vertices is met exactly. Each Moore graph has girth exactly {{math|2''k'' + 1}}: it does not have enough vertices to have higher girth, and a shorter cycle would cause there to be too few vertices in the first {{mvar|k}} levels of some breadth first search tree.
Therefore, any Moore graph has the minimum number of vertices possible among all graphs with minimum degree {{mvar|d}} and girth {{math|2''k'' + 1}}: it is a [[Cage (graph theory)|cage]].

For even girth {{math|2''k''}}, one can similarly form a breadth-first search tree starting from the midpoint of a single edge. The resulting bound on the minimum number of vertices in a graph of this girth with minimum degree {{mvar|d}} is
:<math>2\sum_{i=0}^{k-1}(d-1)^i=1+(d-1)^{k-1}+d\sum_{i=0}^{k-2}(d-1)^i.</math>
(The right hand side of the formula instead counts the number of vertices in a breadth first search tree starting from a single vertex, accounting for the possibility that a vertex in the last level of the tree may be adjacent to {{mvar|d}} vertices in the previous level.)
Thus, the Moore graphs are sometimes defined as including the graphs that exactly meet this bound. Again, any such graph must be a cage.

== Examples ==

The '''Hoffman–Singleton theorem''' states that any Moore graph with girth 5 must have degree 2, 3, 7, or 57. The Moore graphs are:{{sfnp|Bollobás|1998|loc=Theorem 19, p. 276}}

* The [[Complete graph|complete graph]]s {{mvar|K{{sub|n}}}} on {{math|''n'' > 2}} nodes (diameter 1, girth 3, degree {{math|''n'' − 1}}, order {{mvar|n}})
* The odd [[Cycle graph|cycles]] {{math|''C''{{sub|2''n''+1}}}} (diameter {{mvar|n}}, girth {{math|2''n'' + 1}}, degree 2, order {{math|2''n'' + 1}})
* The [[Petersen graph]] (diameter 2, girth 5, degree 3, order 10)
* The [[Hoffman–Singleton graph]] (diameter 2, girth 5, degree 7, order 50)
* A hypothetical graph (or more than one) of diameter 2, girth 5, degree 57 and order 3250, whose existence is unknown.{{sfnp|Dalfó|2019}}

Although all the known Moore graphs are [[Vertex-transitive graph|vertex-transitive graph]]s, the unknown one (if it exists) cannot be vertex-transitive, as its automorphism group can have order at most 375, less than its number of vertices.{{sfnp|Mačaj|Širáň|2010}}

If the generalized definition of Moore graphs that allows even girth graphs is used, the even girth Moore graphs correspond to incidence graphs of (possible degenerate) [[Generalized polygon]]s.  Some examples are the even cycles {{math|''C''{{sub|2''n''}}}}, the [[Complete bipartite graph|complete bipartite graph]]s {{math|''K''{{sub|''n'',''n''}}}} with girth four, the [[Heawood graph]] with degree 3 and girth 6, and the [[Tutte–Coxeter graph]] with degree 3 and girth 8. More generally, it is known that, other than the graphs listed above, all Moore graphs must have girth 5, 6, 8, or 12.<ref>{{harvtxt|Bannai|Ito|1973}}; {{harvtxt|Damerell|1973}}</ref> The even girth case also follows from the Feit-Higman theorem about possible values of {{mvar|n}} for a generalized {{mvar|n}}-gon.

==See also==
* Table of the largest known graphs of a given diameter and maximal degree

==Notes==
{{reflist}}

== References ==
* {{citation
  | title = Moore Graphs and Cycles Are Extremal Graphs for Convex Cycles
  | last1 = Azarija
  | first1 = Jernej
  | last2 = Klavžar
  | first2 = Sandi
  | journal = Journal of Graph Theory
  | volume = 80
  | pages = 34–42
  | year = 2015
  | doi = 10.1002/jgt.21837| arxiv = 1210.6342
  | s2cid = 333785
 }}
* {{citation
 |last1       = Bannai
 |first1      = E.
 |last2       = Ito
 |first2      = T.
 |title       = On finite Moore graphs
 |url         = http://repository.dl.itc.u-tokyo.ac.jp/dspace/handle/2261/6123
 |journal     = Journal of the Faculty of Science, the University of Tokyo. Sect. 1 A, Mathematics
 |volume      = 20
 |pages       = 191–208
 |year        = 1973
 |mr          = 0323615
 |url-status     = dead
 |archiveurl  = https://web.archive.org/web/20120424231252/http://repository.dl.itc.u-tokyo.ac.jp/dspace/handle/2261/6123
|archive-date = 2012-04-24
 }}
* {{citation
 | publisher = [[Physics:Springer-Verlag|Springer-Verlag]]
 | series = [[Graduate Texts in Mathematics]]
 | title = Modern Graph Theory
 | volume = 184
 | year = 1998}}.
*{{citation
 | last = Dalfó | first = C.
 | doi = 10.1016/j.laa.2018.12.035
 | journal = Linear Algebra and Its Applications
 | mr = 3901732
 | pages = 1–14
 | title = A survey on the missing Moore graph
 | volume = 569
 | year = 2019| hdl = 2117/127212
 | s2cid = 126689579
 | hdl-access = free
 | url = https://upcommons.upc.edu/bitstream/2117/127212/1/monster%2818oct2017-rev30dec2018%29.pdf
 }}
* {{citation
  | last = Damerell
  | first = R. M.
  | title = On Moore graphs
  | journal = Mathematical Proceedings of the Cambridge Philosophical Society
  | volume = 74
  | issue = 2
 | pages = 227–236
  | year = 1973
  | mr = 0318004
  | doi = 10.1017/S0305004100048015| bibcode = 1973PCPS...74..227D
  }}
*{{citation
 | last1 = Erdős
 | first1 = Paul
 | last2 = Rényi
 | first2 = Alfréd
 | last3 = Sós
 | first3 = Vera T.
 | journal = Studia Sci. Math. Hungar.
 | pages = 215–235
 | title = On a problem of graph theory
 | url = http://www.math-inst.hu/~p_erdos/1966-06.pdf
 | volume = 1
 | year = 1966
 | access-date = 2010-02-23
 | archive-url = https://web.archive.org/web/20160309214909/http://www.math-inst.hu/~p_erdos/1966-06.pdf
 | archive-date = 2016-03-09
 | url-status = dead
 }}.
* {{citation
  | last1 = Hoffman
  | first1 = Alan J.
  | last2 = Singleton
  | first2 = Robert R.
  | title = Moore graphs with diameter 2 and 3
  | journal = IBM Journal of Research and Development
  | volume = 5
  | issue = 4
  | year = 1960
  | pages = 497–504
  | doi = 10.1147/rd.45.0497
  | mr = 0140437}}
*{{citation
 | last1 = Mačaj | first1 = Martin  
 | last2 = Širáň | first2 = Jozef
 | journal = [[Linear Algebra and Its Applications]]
 | pages = 2381–2398
 | title = Search for properties of the missing Moore graph
 | volume = 432
 | issue = 9 
 | year = 2010
 | doi=10.1016/j.laa.2009.07.018| doi-access = free}}.
* {{citation
  | title = There is no irregular Moore graph
  | last = Singleton
  | first = Robert R.
  | journal = [[American Mathematical Monthly]]
  | volume = 75
  | issue = 1
  | pages = 42–43
  | year = 1968
  | mr = 0225679
  | doi = 10.2307/2315106| jstor = 2315106
 }}

== External links ==
* Brouwer and Haemers: [http://homepages.cwi.nl/~aeb/math/ipm/ipm.pdf Spectra of graphs]
* {{MathWorld2|urlname=MooreGraph|title=Moore Graph|urlname2=Hoffman-SingletonTheorem|title2=Hoffman-Singleton Theorem}}

[[Category:Graph families]]
[[Category:Regular graphs]]

{{Sourceattribution|Moore graph}}