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

An equivalent definition of a Moore graph is that it is a graph of diameter *k* with girth 2*k* + 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 (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.

Read more about Moore Graph: Bounding Vertices By Degree and Diameter, Moore Graphs As Cages, Examples

### Other articles related to "moore graph, moore graphs, graphs, graph":

**Moore Graph**- 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 The complete

**graphs**on n > 2 nodes ... (diameter n, girth 2n+1, degree 2, order 2n+1) The Petersen

**graph**...

### Famous quotes containing the words graph and/or moore:

“When producers want to know what the public wants, they *graph* it as curves. When they want to tell the public what to get, they say it in curves.”

—Marshall McLuhan (1911–1980)

“If a large city can, after intense intellectual efforts, choose for its mayor a man who merely will not steal from it, we consider it a triumph of the suffrage.”

—Frank *Moore* Colby (1865–1925)