Moore graph: Difference between revisions

In [[graph theory]], a '''Moore graph''' is a [[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 [[Vertexvertex (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>

[[Image:Petersen-as-Moore.svg|thumb|The [[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

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]].

:<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.)

* A hypothetical graph (or more than one) of diameter 2, girth 5, degree 57 and order 3250,; whosethe existence of such is unknown and is one of the most famous [[open problem]]s in graph theory.{{sfnp|Dalfó|2019}}

Although all the known Moore graphs are [[vertex-transitive graph]]s, the unknown one (if it exists) cannot be vertex-transitive, as its [[automorphism group]] can have [[order (group theory)|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) [[Generalizedgeneralized polygon]]s. Some examples are the even cycles {{math|''C''{{sub|2''n''}}}}, the [[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.