Degree Diameter Problem

The Degree--Diameter Extremal Problem

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

For integers $d,k\geq1$, let $N(d,k)$ be the maximum number of vertices of a finite connected simple graph of maximum degree at most $d$ and diameter at most $k$. Diameter is the maximum, over vertex pairs, of their shortest-path distance in edges. Determine $N(d,k)$ over the parameter range rather than restricting to regular or vertex-transitive graphs. [S1] [S2]

Statement recorded in the supplied source.

For given maximum degree d and diameter k, what is the largest possible number of vertices in a graph? [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Determine exact values for the many non-optimal table entries and improve general constructions or upper bounds away from the Moore cases. [S1]

Short English statement

How many vertices can a connected graph have when both the maximum degree and the greatest shortest-path distance are prescribed?

Research attempt

Target and interpretation of tabulated constructions.

The quantity is maximized over all connected simple graphs, including irregular and asymmetric graphs. The primary description of Comellas's version-11 table [E1] distinguishes its largest known constructions from entries proved optimal. This attempt derives universal bounds and several exact cases; it does not treat every construction in a table as an exact value of $N(d,k)$.

The breadth-first bound with all small cases separated.

For $d\ge2$, fix a vertex $x$ and expose vertices by distance from it. There is at most one vertex at distance zero, at most $d$ at distance one, and at most $d(d-1)^{i-1}$ at distance $i\ge1$. Every discovered vertex other than $x$ has at least one incident edge leading to an earlier layer and hence at most $d-1$ edges available to discover new vertices. Collisions only reduce the layer sizes. Since the diameter is at most $k$, \[ N(d,k)\le M(d,k):=1+d\sum_{i=0}^{k-1}(d-1)^i. \] For $d>2$ this is $1+d((d-1)^k-1)/(d-2)$; retaining the sum avoids a meaningless division at $d=2$. At $d=1$, a connected simple graph has at most two vertices, and $K_2$ attains the bound for every $k\ge1$, so $N(1,k)=2$.

At diameter one every distinct pair must be adjacent. Thus $N(d,1)=d+1$, attained by $K_{d+1}$. At degree two, a connected graph is a path or a cycle (or a single vertex). A path of diameter at most $k$ has at most $k+1$ vertices, and a cycle of order $m$ has diameter $\lfloor m/2\rfloor$. The cycle $C_{2k+1}$ therefore attains the breadth-first bound: \[ N(2,k)=2k+1. \] This also gives the correct $N(2,1)=3$.

An exact nontrivial case: $N(3,2)=10$.

Use the ten two-element subsets of a five-element set as vertices, joining two subsets when they are disjoint. A fixed subset has three disjoint two-element subsets in its three-element complement, so the graph is cubic. Two distinct nonadjacent vertices intersect in one element; their union has three elements, and its two-element complement is their unique common neighbour. Thus every pair is at distance at most two. The graph has ten vertices, while $M(3,2)=1+3+6=10$. Consequently it is optimal. This is the Petersen graph, derived here from its subset model without assuming its extremality.

General constructions with controlled parameters.

For an integer $q\ge2$, take words of length $k$ over an alphabet of size $q$, joining words that differ in exactly one position. There are $q^k$ vertices, the degree is $k(q-1)$, and the distance between two words equals the number of positions in which they differ. The upper bound on the distance follows by changing those positions one at a time; the lower bound follows because one edge changes only one position. Choosing $q=\lfloor d/k\rfloor+1$ gives \[ N(d,k)\ge (\lfloor d/k\rfloor+1)^k \quad\hbox{when }d\ge k. \] The graph has diameter exactly $k$. This is only a useful lower bound in part of the parameter range, and the complete-graph lower bound $N(d,k)\ge d+1$ remains available for every $k\ge1$.

A different word construction handles other ratios. For $q\ge2$, join each word $(a_1,\ldots,a_k)$ to each word $(a_2,\ldots,a_k,b)$ and make the edges undirected, deleting loops and duplicate edges. There are at most $q$ successors and $q$ predecessors, so the maximum degree is at most $2q$. Starting with any word, append the $k$ symbols of a target word in order; after at most $k$ edge moves the target is reached. A repeated word in this walk merely deletes a loop step. Thus for $d\ge4$, \[ N(d,k)\ge\lfloor d/2\rfloor^k. \] Neither construction is asserted to give the largest currently known graph for an individual pair $(d,k)$.

What equality would force.

Attaining the breadth-first bound means every allowable child slot in every layer is occupied by a distinct vertex. At $k=2$, this forces every vertex to have degree $d$, no triangles, and no four-cycles. For example two neighbours of the root cannot be joined, since that wastes a child slot; nor can a second-layer vertex have two parents. As every nonadjacent pair must then have exactly one common neighbour, the adjacency matrix satisfies \[ A^2=(d-1)I-A+J. \] This provides necessary algebraic restrictions on equality, but it does not determine the best order when equality is impossible. An upper bound excluding $M(d,k)$ leaves all smaller candidate orders to be compared with actual constructions.

Executed checks and explicit residual task.

The graph script constructs the subset model, checks every distance, and obtains order ten, constant degree three, and diameter two. It also checks its common-neighbour counts. The files are checks_graphs.py and results_graphs.json in _Local/Erdos_problems/UnsolvedMath/attempt_audit_2026_10_01/number_theory/. No enumeration over all graph orders or all parameter pairs is claimed. The exact answers above cover $d=1$, $d=2$, $k=1$, and $(d,k)=(3,2)$; the general inequalities leave a substantial gap elsewhere. Determining that gap requires either stronger universal exclusions or constructions meeting them, not just a larger sample of symmetric graphs. Outcome: UNRESOLVED for the catalogue-wide extremal problem.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1412 (GRAPH-025), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 F. Comellas, Table of Large Degree/Diameter Graphs, Mendeley Data, version 11 (January 2026). https://doi.org/10.17632/d75dzbjd4k.11. Bibliographic information from the supplied record.

• E1 Francesc Comellas, Table of Large Degree/Diameter Graphs, Mendeley Data, version 11, 28 January 2026. https://data.mendeley.com/datasets/d75dzbjd4k/11. Primary dataset description inspected 1 October 2026; it explicitly distinguishes optimal entries from largest known constructions.