← All problems

Degree diameter problem

65 years old · documented by

For a finite simple undirected graph GG let ∣V(G)∣|V(G)| denote its number of vertices, Δ(G)\Delta(G) its maximum degree, and diam⁡(G)\operatorname{diam}(G) its diameter (the maximum, over all pairs of vertices, of the length of a shortest path joining them). For positive integers dd and kk set

nd,k=max⁡{ ∣V(G)∣:G finite simple undirected, Δ(G)≤d, diam⁡(G)≤k },n_{d,k}=\max\bigl\{\,|V(G)| : G \text{ finite simple undirected},\ \Delta(G)\le d,\ \operatorname{diam}(G)\le k\,\bigr\},

and let

Md,k=1+d∑i=0k−1(d−1)i={1+d(d−1)k−1d−2,d>2,2k+1,d=2,M_{d,k}=1+d\sum_{i=0}^{k-1}(d-1)^{i}=\begin{cases}1+d\dfrac{(d-1)^{k}-1}{d-2}, & d>2,\\[6pt] 2k+1, & d=2,\end{cases}

so that nd,k≤Md,kn_{d,k}\le M_{d,k} for all d,k≥1d,k\ge 1, and nd,1=d+1n_{d,1}=d+1, n1,k=2n_{1,k}=2, n2,k=2k+1n_{2,k}=2k+1.

Determine nd,kn_{d,k} for all integers d,k≥2d,k\ge 2. In particular, for every fixed integer k≥2k\ge 2,

lim⁡d→∞nd,kdk=1,\lim_{d\to\infty}\frac{n_{d,k}}{d^{k}}=1,

equivalently nd,k=(1−o(1)) Md,kn_{d,k}=(1-o(1))\,M_{d,k} as d→∞d\to\infty with kk fixed; that is, writing μk=lim inf⁡d→∞nd,k/dk\mu_{k}=\liminf_{d\to\infty} n_{d,k}/d^{k}, one has μk=1\mu_{k}=1 for every k≥2k\ge 2.

A graph GG with Δ(G)≤d\Delta(G)\le d, diam⁡(G)≤k\operatorname{diam}(G)\le k and ∣V(G)∣=Md,k|V(G)|=M_{d,k} is a Moore graph; such a graph is necessarily dd-regular. There exists a Moore graph with d=57d=57 and k=2k=2, i.e. a 5757-regular graph on M57,2=3250M_{57,2}=3250 vertices of diameter 22.

References
  1. Wikipedia, Degree diameter problem, the article this problem comes from.

Source: Wikipedia

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.