Degree Diameter

In graph theory, the degree diameter problem is the problem of finding the largest possible graph (in terms of the size of its vertex set ) of diameter such that the largest degree of any of the vertices in is at most . The size of is bounded above by the Moore bound; for and only the Petersen graph, the Hoffman-Singleton graph, and possibly one more graph (not yet proven to exist) of diameter and degree attain the Moore bound. In general, the largest degree-diameter graphs are much smaller in size than the Moore bound.

Formula

Let $n_$ be the maximum possible number of vertices for a graph with degree at most ''d'' and diameter ''k''. Then $n_\leq M_$, where $M_$ is the Moore bound:

:$M_=\begin1+d\frac&\textd>2\\2k+1&\textd=2\end$

This bound is attained for very few graphs, thus the study moves to how close there exist graphs to the Moore bound.
For asymptotic behaviour note that $M_=d^k+O(d^)$.

Define the parameter $\mu_k=\liminf_\frac$. It is conjectured that $\mu_k=1$ for all ''k''. It is known that $\mu_1=\mu_2=\mu_3=\mu_5=1$ and that $\mu_4\geq 1/4$.

See also

* Cage (graph theory)
* Table of degree diameter graphs
* Table of vertex-symmetric degree diameter digraphs
* Maximum degree-and-diameter-bounded subgraph problem

References

*

*

*

*

* {{citation
, title = CombinatoricsWiki - The Degree/Diameter Problem
, url = http://combinatoricswiki.org/wiki/The_Degree/Diameter_Problem

Computational problems in graph theory
Graph distance