Bounding Vertices By Degree and Diameter
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 ≤ i ≤ k, there can be at most d(d-1)i vertices. Thus, the total number of vertices can be at most
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 2k+1; these two requirements combine to force the graph to be d-regular for some d and to satisfy the vertex-counting formula.
Read more about this topic: Moore Graph
Famous quotes containing the words bounding and/or degree:
“I fell her finger light
Laid pausefully upon lifes headlong train;
The foot less prompt to meet the morning dew,
The heart less bounding at emotion new,
And hope, once crushd, less quick to spring again.”
—Matthew Arnold (18221888)
“A certain degree of fear produces the same effects as rashness.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (16941773)