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 2k + 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":
... 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 ... 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)
“‘Twas that friends, the belov’d of my bosom, were near,
Who made every dear scene of enchantment more dear,”
—Thomas Moore (1779–1852)