Metric dimension (graph theory)¶

The minimum size of a vertex subset whose distance vectors uniquely identify every graph vertex.

Version: v2 · 2026-09-06 · History
Domain-specific #: 2268
Origin domain: mathematics
Subdomain: graph distances and resolving sets
Aliases: Graph metric dimension, Location number

Core Idea¶

Metric dimension (graph theory) is the minimum size of a vertex subset whose distance vectors uniquely identify every graph vertex.

For an ordered landmark set S in a connected graph, each vertex receives the vector of shortest-path distances to the landmarks. S resolves the graph when all vertices have distinct vectors. The graph's metric dimension is the minimum cardinality of such a resolving set, and a minimum set is a metric basis.

Its operative boundary is not supplied by the name alone. Preserve this identity: The minimum size of a vertex subset whose distance vectors uniquely identify every graph vertex. Validity boundary: Every vertex must have a unique ordered distance representation to the selected landmarks, and the set must be minimum-cardinality.

Scope of Application¶

The abstraction recurs literally within finite connected graphs and variants where vertices or edges must be uniquely located through graph distances. The following habitats preserve the same recognition machinery; they are not invitations to extend the name metaphorically.

Network localization. landmark distances identify node positions.
Robot navigation. distance sensors distinguish graph locations.
Chemical graphs. distance coordinates characterize molecular vertices.
Graph algorithms. minimum resolving sets form an NP-hard optimization problem.
Fault-tolerant variants. redundant landmarks preserve identification after failure.

Clarity¶

Declare graph connectivity, whether distances identify vertices or edges, and whether the variant is local, strong, fractional, or fault tolerant. Distinctness must be checked for every pair, and minimum cardinality requires a lower bound as well as a construction.

A practical identification audit begins with the typed roles rather than the title: establish the connected graph, verify the landmark set, then test the remaining conditions and exclusions.

Manages Complexity¶

A small landmark set compresses vertex identity into distance coordinates. The optimization exposes symmetry: automorphically similar vertices require landmarks that break their indistinguishability.

The compression remains accountable because each simplification has a named failure condition. Disagreement can be localized to a missing role, an invalid assumption, an ambiguous measurement, or a neighboring abstraction instead of being hidden inside an unanalyzed label.

Abstract Reasoning¶

R1. Fix the graph and its shortest-path metric. R2. Choose an ordered candidate landmark set. R3. Compute each vertex's complete distance vector. R4. Check pairwise uniqueness to prove the set resolves. R5. Prove optimality by ruling out every smaller cardinality or using a valid lower bound.

Knowledge Transfer¶

The notion transfers literally to graph-distance localization and named variants with adjusted recognition tests. Measurement and identifiability are parents; a feature embedding that distinguishes nodes is not metric dimension unless its coordinates are landmark distances and minimal.

The transfer boundary is explicit: DOMAIN-SPECIFIC PASS / PRIME FAIL: The invariant is computed across connected graphs, candidate resolving sets, and graph families. Literal recognition retains the specialist vocabulary and validity conditions of graph theory; outside that setting only broader parent operations transfer.

Relationships to Other Abstractions¶

Current abstraction Metric dimension (graph theory) Domain-specific

Parents (2) — more general patterns this builds on

Metric dimension (graph theory) is a kind of Identifiability Prime

Identifiability (prime:identifiability).
Metric dimension (graph theory) is a kind of Measurement Prime

Measurement (prime:measurement).

Hierarchy paths (2) — routes to 2 parentless roots

Metric dimension (graph theory) → Identifiability → Injectivity → Function (Mapping)

Show alternative path (1)

Neighborhood in Abstraction Space¶

Metric dimension (graph theory) sits in a sparse region of the domain-specific corpus (67^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

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