Degree diameter problem

Unsolved problem in mathematics

Given two positive integers Template:Mvar, Template:Mvar, what is the largest graph of diameter Template:Mvar such that all vertices have degrees at most Template:Mvar?

More unsolved problems in mathematics

File:Degree-Diameter trivials.png

When the degree is less than or equal to 2 or the diameter is less than or equal to 1, the problem becomes trivial, solved by the cycle graph and complete graph respectively.

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

Formula

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

$M_{d,k}=\{\begin{array}{ll}1+d\frac{(d-1{)}^k-1}{d-2}& \text{ if }d>2\\ 2k+1& \text{ if }d=2\end{array}$

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}=d^k+O(d^{k-1})$.

Define the parameter ${\mu }_k=\underset{d\to \mathrm{\infty }}{\mathrm{lim\; inf}}\frac{n_{d,k}}{d^k}$. 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\ge 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

Template:Hyperbolic-geometry-stub Template:Graph-stub