Moore graph

Last updated November 04, 2023

Unsolved problem in mathematics:

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

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,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);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.

Bounding vertices by degree and diameter

The Petersen graph as a Moore graph. Any breadth first search tree has d(d - 1) vertices in its i-th level for i >= 1. Petersen-as-Moore.svg — The Petersen graph as a Moore graph. Any breadth first search tree has $d (d - 1)$ vertices in its $i$ -th level for $i \geq 1$ .

Let $G$ be any graph with maximum degree $d$ and diameter $k$ , and consider the tree formed by breadth first search starting from any vertex $v$ . This tree has 1 vertex at level 0 ( $v$ itself), and at most $d$ vertices at level 1 (the neighbors of $v$ ). In the next level, there are at most $d (d - 1)$ vertices: each neighbor of $v$ uses one of its adjacencies to connect to $v$ and so can have at most $d - 1$ neighbors at level 2. In general, a similar argument shows that at any level $1 \leq i \leq k$ , there can be at most $d (d - 1) i -1$ vertices. Thus, the total number of vertices can be at most

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

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 $d$ and diameter $k$ .

Later, Singleton (1968) showed that Moore graphs can equivalently be defined as having diameter $k$ and girth $2 k + 1$ ; these two requirements combine to force the graph to be $d$ -regular for some $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.^[2] Suppose $G$ has minimum degree $d$ and girth $2 k + 1$ . Choose arbitrarily a starting vertex $v$ , and as before consider the breadth-first search tree rooted at $v$ . This tree must have one vertex at level 0 ( $v$ itself), and at least $d$ vertices at level 1. At level 2 (for $k > 1$ ), there must be at least $d (d - 1)$ vertices, because each vertex at level 1 has at least $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 $1 \leq i \leq k$ , there must be at least $d (d - 1) i$ vertices. Thus, the total number of vertices must be at least

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

In a Moore graph, this bound on the number of vertices is met exactly. Each Moore graph has girth exactly $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 $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 $d$ and girth $2 k + 1$ : it is a cage.

For even girth $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 $d$ is

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

(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 $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:^[3]

The complete graphs $K n$ on $n > 2$ nodes (diameter 1, girth 3, degree $n - 1$ , order $n$ )
The odd cycles $C 2 n +1$ (diameter $n$ , girth $2 n + 1$ , degree 2, order $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.^[4]

Although all the known Moore graphs are vertex-transitive graphs, 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.^[5]

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 polygons. Some examples are the even cycles $C 2 n$ , the complete bipartite graphs $K 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.^[6] The even girth case also follows from the Feit-Higman theorem about possible values of $n$ for a generalized $n$ -gon.

Notes

Related Research Articles

In graph theory, the girth of an undirected graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles, its girth is defined to be infinity. For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth four or more is triangle-free.

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each internal vertex are equal to each other. A regular graph with vertices of degree $k$ is called a $k$ ‑regular graph or regular graph of degree $k$ . Also, from the handshaking lemma, a regular graph contains an even number of vertices with odd degree.

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets $and, that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.$

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In the mathematical field of graph theory, a spanning treeT of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree. If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T.

<span class="mw-page-title-main">Strongly regular graph</span> Concept in graph theory

In graph theory, a strongly regular graph (SRG) is a regular graph $G = (V, E)$ with $v$ vertices and degree $k$ such that for some given integers

In statistical mechanics and mathematics, the Bethe lattice is an infinite connected cycle-free graph where all vertices have the same number of neighbors. The Bethe lattice was introduced into the physics literature by Hans Bethe in 1935. In such a graph, each node is connected to z neighbors; the number z is called either the coordination number or the degree, depending on the field.

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network.

In the mathematical field of graph theory, the Hoffman–Singleton graph is a 7-regular undirected graph with 50 vertices and 175 edges. It is the unique strongly regular graph with parameters (50,7,0,1). It was constructed by Alan Hoffman and Robert Singleton while trying to classify all Moore graphs, and is the highest-order Moore graph known to exist. Since it is a Moore graph where each vertex has degree 7, and the girth is 5, it is a (7,5)-cage.

In the mathematical field of graph theory, a cage is a regular graph that has as few vertices as possible for its girth.

In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.

In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of $vertices from an n -vertex graph can partition the graph into disjoint subgraphs each of which has at most vertices.$

In graph theory, the degree diameter problem is the problem of finding the largest possible graph $G$ of diameter $k$ such that the largest degree of any of the vertices in $G$ is at most $d$ . The size of $G$ is bounded above by the Moore bound; for $1 < k$ and $2 < d$ only the Petersen graph, the Hoffman-Singleton graph, and possibly graphs of diameter $k = 2$ and degree $d = 57$ attain the Moore bound. In general, the largest degree-diameter graphs are much smaller in size than the Moore bound.

In the mathematical field of graph theory, the odd graphs are a family of symmetric graphs defined from certain set systems. They include and generalize the Petersen graph.

In graph theory, a well-covered graph is an undirected graph in which every minimal vertex cover has the same size as every other minimal vertex cover. Equivalently, these are the graphs in which all maximal independent sets have equal size. Well-covered graphs were defined and first studied by Michael D. Plummer in 1970.

In graph theory, a branch of mathematics, the $k$ th power $G k$ of an undirected graph $G$ is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in $G$ is at most $k$ . Powers of graphs are referred to using terminology similar to that of exponentiation of numbers: $G 2$ is called the square of $G$ , $G 3$ is called the cube of $G$ , etc.

In graph theory, a branch of mathematics, the cop number or copnumber of an undirected graph is the minimum number of cops that suffices to ensure a win in a certain pursuit–evasion game on the graph.

In graph theory, the McKay–Miller–Širáň graphs are an infinite class of vertex-transitive graphs with diameter two, and with a large number of vertices relative to their diameter and degree. They are named after Brendan McKay, Mirka Miller, and Jozef Širáň, who first constructed them using voltage graphs in 1998.

In graph theory, a geodetic graph is an undirected graph such that there exists a unique (unweighted) shortest path between each two vertices.

References

Azarija, Jernej; Klavžar, Sandi (2015), "Moore Graphs and Cycles Are Extremal Graphs for Convex Cycles", Journal of Graph Theory , 80: 34–42, arXiv: 1210.6342 , doi:10.1002/jgt.21837, S2CID 333785
Bannai, E.; Ito, T. (1973), "On finite Moore graphs", Journal of the Faculty of Science, the University of Tokyo. Sect. 1 A, Mathematics, 20: 191–208, MR 0323615, archived from the original on 2012-04-24
Bollobás, Béla (1998), Modern Graph Theory, Graduate Texts in Mathematics, vol. 184, Springer-Verlag .
Dalfó, C. (2019), "A survey on the missing Moore graph" (PDF), Linear Algebra and Its Applications, 569: 1–14, doi:10.1016/j.laa.2018.12.035, hdl: 2117/127212 , MR 3901732, S2CID 126689579
Damerell, R. M. (1973), "On Moore graphs", Mathematical Proceedings of the Cambridge Philosophical Society, 74 (2): 227–236, Bibcode:1973PCPS...74..227D, doi:10.1017/S0305004100048015, MR 0318004
Erdős, Paul; Rényi, Alfréd; Sós, Vera T. (1966), "On a problem of graph theory" (PDF), Studia Sci. Math. Hungar., 1: 215–235, archived from the original (PDF) on 2016-03-09, retrieved 2010-02-23.
Hoffman, Alan J.; Singleton, Robert R. (1960), "Moore graphs with diameter 2 and 3", IBM Journal of Research and Development, 5 (4): 497–504, doi:10.1147/rd.45.0497, MR 0140437
Mačaj, Martin; Širáň, Jozef (2010), "Search for properties of the missing Moore graph", Linear Algebra and Its Applications , 432 (9): 2381–2398, doi: 10.1016/j.laa.2009.07.018 .
Singleton, Robert R. (1968), "There is no irregular Moore graph", American Mathematical Monthly , 75 (1): 42–43, doi:10.2307/2315106, JSTOR 2315106, MR 0225679

External links

Brouwer and Haemers: Spectra of graphs
Weisstein, Eric W., "Moore Graph" ("Hoffman-Singleton Theorem") at MathWorld .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

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

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

[FOOTNOTEBollobás1998Theorem_19,_p._276-3] Bollobás (1998), Theorem 19, p. 276.

[FOOTNOTEDalfó2019-4] Dalfó (2019).

[FOOTNOTEMačajŠiráň2010-5] Mačaj & Širáň (2010).

[6] Bannai & Ito (1973); Damerell (1973)

[1]

[2]

[3]

[4]

[5]

[6]