Degree diameter problem¶

Maximize the number of vertices in a finite graph subject to simultaneous maximum-degree and diameter bounds, comparing constructions with the breadth-first Moore upper bound.

Version: v1 · 2026-08-30 · History
Domain-specific #: 1635
Origin domain: mathematics
Subdomain: extremal graph order under degree and diameter
Aliases: Degree–diameter problem, Degree/diameter problem

Core Idea¶

The degree–diameter problem asks, for positive integers \(d\) and \(k\), for the maximum possible order \(n(d,k)\) of a finite simple undirected graph whose maximum degree is at most \(d\) and whose diameter is at most \(k\). The objective is vertex count; degree and diameter are simultaneous constraints. Variants for directed, bipartite, planar, vertex-transitive, or other graph classes must be labeled because their bounds and extremizers differ.^[1]

A breadth-first expansion from one vertex gives the Moore bound. For \(d>2\), at most \(1+d\sum_{i=0}^{k-1}(d-1)^i\) vertices can lie within distance \(k\): one root, at most \(d\) neighbors, and at most \(d-1\) new branches at each later level. Collisions and cycles prevent most graphs from realizing the tree count. Research attacks from above by proving tighter impossibility bounds and from below by constructing large graphs, often using algebraic or computational methods. Equality defines exceptional Moore graphs rather than the generic solution.^[2]

This is not the cage problem, which minimizes order for fixed regular degree and girth. It is not simply computing the diameter of a given graph or maximizing degree at fixed order. Maximum degree at most d differs from regular degree exactly d, though extremal constructions are often regular. Directed diameter requires strong reachability and a different Moore expression. Published largest-known tables contain lower bounds unless optimality is proved, so record constructions must not be reported as exact values.^[3]

Structural Signature¶

Graph class. Finite simple undirected graphs provide the default feasible objects.
Degree bound. No vertex may have degree exceeding \(d\).
Diameter bound. Every pair of vertices must be connected by a path of length at most \(k\).
Order objective. The number of vertices is maximized.
Moore upper bound. Breadth-first counting supplies a universal feasibility ceiling.
Construction. An explicit graph gives a certified lower bound on \(n(d,k)\).
Impossibility argument. Additional combinatorial restrictions can lower the upper bound.
Optimality gap. The difference between best construction and best bound measures unresolved space.

What It Is Not¶

Not the cage problem. Cages minimize order under degree and girth, a different extremal direction.
Not diameter computation. Evaluating one graph does not optimize over all feasible graphs.
Not Moore graph classification. Moore graphs are rare equality cases within the wider problem.
Not a regular-only problem. The standard constraint is maximum degree, although regular extremizers often arise.
Not a directed problem by default. Digraph variants use directed distance and different bounds.
Not a largest-known equals optimum claim. A construction proves only a lower bound until matched by an upper bound.

Scope of Application¶

The abstraction is literal wherever practitioners can identify the same constitutive roles, apply the same boundary tests, and obtain the same kind of output. The following habitats are uses of Degree diameter problem itself, not metaphors based only on resemblance.

Extremal graph theory. Determining exact values or bounds for selected degree–diameter pairs.
Network topology. Designing many-node networks with bounded port count and hop distance.
Algebraic constructions. Using groups, finite fields, and incidence geometry to build large graphs.
Computational search. Finding record graphs or excluding candidates for small parameters.
Restricted graph classes. Studying planar, bipartite, Cayley, or vertex-transitive variants.
Asymptotic analysis. Comparing growth in d or k with Moore-order scaling.

Clarity¶

A clear account of Degree diameter problem must preserve the recognition invariant stated in the Core Idea rather than rely on the title alone. State directedness, simplicity, degree convention, diameter convention, and any restricted graph class. Distinguish exact optimum, lower bound from construction, upper bound, and asymptotic statement. Derive the correct Moore bound for exceptional cases such as d equal to two. Provide an adjacency, algebraic, or cited construction before claiming a record lower bound. These declarations are not editorial extras: each changes what observations count, which transformations are licensed, and what conclusion can be drawn. A reader should be able to reconstruct the input, the operative rule, the output, and at least one defeater from the account without consulting an implementation or guessing an unstated convention.

Manages Complexity¶

Degree diameter problem manages complexity by replacing a diffuse field of observations or possible operations with a bounded role structure: graph class supplies finite simple undirected graphs provide the default feasible objects.; degree bound supplies no vertex may have degree exceeding \(d\).; diameter bound supplies every pair of vertices must be connected by a path of length at most \(k\).; order objective supplies the number of vertices is maximized.; moore upper bound supplies breadth-first counting supplies a universal feasibility ceiling.. The compression is useful because it localizes disagreement. One can ask whether the input was properly formed, whether a constitutive relation held, whether an alternative explanation defeats the inference, or whether the output was overinterpreted. The same compression can mislead when its discarded detail is exactly what the decision requires. A reference-grade use therefore reports both the invariant retained and the information intentionally lost.

Abstract Reasoning¶

Fix \(d\), \(k\), and the admissible graph class.
Derive the breadth-first Moore ceiling for those conventions.
Check known equality obstructions and stronger upper bounds.
Construct or retrieve a graph and verify maximum degree, connectivity, diameter, and order.
Compare its order with the current certified upper bound.
Use symmetry or algebraic structure to reduce verification without assuming optimality.
Report exactness only when lower and upper bounds coincide.
Test the candidate interpretation against the nearest named confusable rather than accepting a shared surface feature.
State the conclusion at the same scope as the source conditions, and retain uncertainty or nonuniqueness where the construct does not remove it.

Knowledge Transfer¶

The strict upward abstraction is Optimization. Degree Diameter Problem instantiates Optimization because it seeks the maximum graph order among objects satisfying simultaneous degree and diameter constraints. Within extremal graph order under degree and diameter, the full mechanism transfers literally when the same roles and boundary tests recur. Beyond that domain, only the parent-level skeleton should travel. Reusing the label Degree diameter problem after removing its constitutive vocabulary would hide a change of mechanism behind an analogy. The honest transfer rule is therefore two-stage: recognize the domain-specific pattern first, then lift only the parent relation that remains invariant under a substrate change.

Examples¶

Canonical¶

For \(d=3\) and \(k=2\), the Moore expression gives \(1+3+3(2)=10\). The Petersen graph has ten vertices, is cubic, and has diameter two, so it meets the upper bound and proves \(n(3,2)=10\). For another parameter pair, producing a graph close to the Moore bound establishes a lower bound but cannot prove the exact maximum unless a matching impossibility result is available.

Mapped back: input and conventions → constitutive role test → bounded output → explicit interpretation and defeater check.

Applied / In Practice¶

A communication designer allows at most six links per node and at most three hops between any pair. A symmetric graph construction yields many nodes and predictable routing, but the abstract degree–diameter objective ignores link reliability, congestion, cable length, and routing policy. The graph gives a topology benchmark; an engineered network must add those constraints rather than treating maximum order as complete design optimality.

Mapped back: field observation or problem → candidate recognition → confusable and limit checks → appropriately scoped conclusion.

Structural Tensions¶

T1: Tree expansion versus cycle closure. The Moore count assumes every breadth-first branch reaches new vertices. Diagnostic: Count forced collisions at each level before claiming attainability.
T2: Record construction versus exact optimum. A largest known graph may later be improved. Diagnostic: Label every number as construction, bound, or equality theorem.
T3: Maximum degree versus regularity. The constraint permits low-degree vertices even when constructions are regular. Diagnostic: Verify the actual quantified degree condition.
T4: Undirected versus directed distance. Reachability and bounds change with arc orientation. Diagnostic: State the graph species before using a table.
T5: Mathematical order versus engineering value. More vertices can worsen robustness or congestion. Diagnostic: Keep operational objectives outside the pure extremal conclusion.
T6: Autonomy versus Optimization. Optimization supplies best-under-constraints, while this problem fixes graph order, degree, diameter, and Moore diagnostics. Diagnostic: Remove the graph parameters and test whether only generic optimization remains.

Structural–Framed Character¶

The degree–diameter problem is strongly structural: feasibility and objective are exact, while record status and the engineering value of constructions depend on dated evidence and external requirements. The five framing criteria point in a consistent direction. Evaluative weight is limited to whether the defining conditions are met, not whether the outcome is desirable. Human practice matters to the extent that experts choose conventions, instruments, or reporting thresholds, but those choices do not make every verdict arbitrary. Institutional history explains the name and standard use; it does not replace the recognition rule. The operative vocabulary travels within the home field and closely adjacent subfields, while transfer farther away requires translation to the parent prime. Thus recognition remains disciplined even where interpretation is defeasible.

Structural Core vs. Domain Accent¶

What is skeletal. Degree Diameter Problem instantiates Optimization because it seeks the maximum graph order among objects satisfying simultaneous degree and diameter constraints. This is the part that can be expressed without the candidate's specialist nouns.

What is domain-bound. The irreducible accent is finite graph order, maximum degree, shortest-path diameter, breadth-first Moore bounds, exceptional equality, constructive lower bounds, and impossibility upper bounds. Remove those elements and the result is no longer Degree diameter problem; it is only the parent relation or a loose analogy.

Why this does not clear the prime bar. The name does not recur with unchanged diagnostics across three independent domains. What transfers is already represented by prime:optimization. The candidate remains autonomous because its in-domain recognition rule, failure modes, and consequences are stable, but its vocabulary and interventions do not float free of the home substrate.

Degree Diameter Problem instantiates Optimization because it seeks the maximum graph order among objects satisfying simultaneous degree and diameter constraints.

The prospective workspace queue contains one strict upward edge to prime:optimization. No live DAG mutation is authorized.

Relationships to Other Abstractions¶

Current abstraction Degree diameter problem Domain-specific

Parents (1) — more general patterns this builds on

Degree diameter problem is a kind of Optimization Prime

Degree Diameter Problem instantiates Optimization because it seeks the maximum graph order among objects satisfying simultaneous degree and diameter constraints.

Hierarchy path (1) — routes to 1 parentless root

Degree diameter problem → Optimization

Neighborhood in Abstraction Space¶

Degree diameter problem sits in a sparse region of the domain-specific corpus (78^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Graph Density, Distance & Planarity (11 abstractions)

Nearest neighbors

Cage (Graph Theory) — 0.87
Dense Graph — 0.82
Matching — 0.82
Planarity — 0.82
Pathwidth — 0.82

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Cage problem. Minimizes order for fixed degree and girth.
Moore graph. An exceptional graph attaining a Moore bound.
Graph diameter. A property of one graph rather than an extremal family problem.
Maximum-degree problem. Does not include the global distance constraint.
Network design. Adds reliability, cost, traffic, and routing objectives.
Order–degree problem. Fixes other parameters and asks a differently oriented extremal question.

References¶

[1] Miller, M., and Širáň, J. (2013). 'Moore Graphs and Beyond: A Survey of the Degree/Diameter Problem.' Electronic Journal of Combinatorics, Dynamic Survey DS14. https://doi.org/10.37236/35 registry ↩

[2] Hoffman, A. J., and Singleton, R. R. (1960). 'On Moore Graphs with Diameters 2 and 3.' IBM Journal of Research and Development 4(5), 497–504. https://doi.org/10.1147/rd.45.0497 registry ↩

[3] Biggs, N. (1993). Algebraic Graph Theory, 2^nd ed. Cambridge University Press. https://doi.org/10.1017/CBO9780511608704 registry ↩