Moore graph information

Unsolved problem in mathematics:

Does a Moore graph with girth 5 and degree 57 exist?

(more unsolved problems in mathematics)

In graph theory, a Moore graph is a regular graph whose girth (the shortest cycle length) is more than twice its diameter (the distance between the farthest two vertices). If the degree of such a graph is $d$ and its diameter is $k$ , its girth must equal $2 k + 1$ . This is true, for a graph of degree $d$ and diameter $k$ , if and only if its number of vertices equals

1+d\sum _{i=0}^{k-1}(d-1)^{i},

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 for their parameters.

Another equivalent definition of a Moore graph $G$ is that it has girth $g = 2 k + 1$ and precisely $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}n/g(m – n + 1)$ cycles of length $g$ , where $n$ and $m$ are, respectively, the numbers of vertices and edges of $G$ . They are in fact extremal with respect to the number of cycles whose length is the girth of the graph.^[1]

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.^[2] 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.

^ Azarija & Klavžar (2015).
^ Erdős, Rényi & Sós (1966).

[FOOTNOTEAzarijaKlavžar2015-1] Azarija & Klavžar (2015).

[FOOTNOTEErdősRényiSós1966-2] Erdős, Rényi & Sós (1966).

Moore graph information

and 16 Related for: Moore graph information

Moore graph

Petersen graph

Glossary of graph theory

Complete bipartite graph

Regular graph

Strongly regular graph

Moore neighborhood

List of unsolved problems in mathematics

Laplacian matrix

McGee graph

Degree diameter problem

State diagram

Graph paper

Table of the largest known graphs of a given diameter and maximal degree

Graph isomorphism problem

Misleading graph