Degree Diameter Problem

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 graphs (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 the largest known graphs of a given diameter and maximal degree
* Table of vertex-symmetric degree diameter digraphs
* Maximum degree-and-diameter-bounded subgraph problem

References

*
*
*
*
*

Computational problems in graph theory
Graph distance

{{graph-stub