This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (November 2024) (Learn how and when to remove this message)

In graph theory, the degree diameter problem is the problem of finding the largest possible graph G (in terms of the size of its vertex set V) of diameter k such that the largest degree of any of the vertices in G is at most d. The size of G 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.

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

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

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

Define the parameter ${\displaystyle \mu _{k}=\liminf _{d\to \infty }{\frac {n_{d,k}}{d^{k}}}}$. It is conjectured that ${\displaystyle \mu _{k}=1}$ for all k. It is known that ${\displaystyle \mu _{1}=\mu _{2}=\mu _{3}=\mu _{5}=1}$ and that ${\displaystyle \mu _{4}\geq 1/4}$.

• 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

This hyperbolic geometry-related article is a stub. You can help Wikipedia by adding missing information.

• v
• t
• e

This graph theory-related article is a stub. You can help Wikipedia by adding missing information.

• v
• t
• e