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. ^[1]

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. The entry therefore captures a reusable specialist role structure rather than a topic label, a single historical instance, or a loose analogy.

Structural Signature¶

Sig role-phrases:

the connected graph — the vertex and edge structure supplying shortest-path distance
the landmark set — selected vertices used as references
the landmark order — a fixed coordinate order for distance vectors
the distance representation — the vector of distances from a vertex to each landmark
the resolving condition — distinct vertices receive different vectors
the cardinality objective — the number of landmarks to minimize
the metric basis — a resolving set attaining the minimum

Recognition test. A case qualifies only when the analyst can map the declared the connected graph, the landmark set, the landmark order, the distance representation, the resolving condition and preserve the specialist validity conditions. Shared vocabulary, a similar output, or a generic instance of one parent relation is insufficient.

What It Is Not¶

Not graph dimension in general. Several unrelated notions of graph dimension exist.
Not a merely dominating set. Every vertex being near a selected vertex does not guarantee unique distance vectors.
Not a locating-dominating set. That variant uses neighborhood codes and domination constraints.
Not Euclidean embedding dimension. No geometric embedding is required.
Not an inclusion-minimal resolving set. Metric dimension uses minimum cardinality, not only irredundancy.

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. If the case retains only the portable skeleton described below, it should be named through a parent abstraction rather than as Metric dimension (graph theory).

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.

These moves separate definition, derivation, measurement, and interpretation. A formal consequence does not by itself prove that an observed case instantiates the abstraction, while an observed resemblance does not relax the formal or institutional recognition conditions.

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. The safe move beyond the home habitat is to carry the applicable parent relation and leave the specialist name behind unless every defining role remains literal.

Examples¶

Canonical: a path graph¶

One endpoint resolves a finite path because distance from that endpoint is different at every vertex. No empty set can distinguish more than one vertex, so a nontrivial path has metric dimension one. ^[1]

Mapped back: the connected graph; the landmark set; the distance representation; the resolving condition; the cardinality objective.

Applied / In Practice: resolving a symmetric graph¶

In a complete graph, vertices outside the landmark set have identical distance one to every landmark. All but one vertex must therefore be selected, giving metric dimension n−1. ^[2]

Mapped back: the landmark set; the distance representation; the resolving condition; the metric basis.

Structural Tensions¶

T1: Resolving vs minimizing. A large set trivially identifies vertices while optimality is the hard part. Diagnostic: Is a lower bound proved?

T2: Symmetry vs landmark economy. Automorphisms create vertices with identical distance profiles. Diagnostic: Which landmarks break each equivalence class?

T3: Connected definition vs infinite distance. Disconnected graphs require a convention or a variant. Diagnostic: Is the distance vector finite and defined?

T4: Ordered vector vs unordered distances. Coordinate identity matters even though set cardinality does not. Diagnostic: Is landmark order fixed consistently?

T5: Classical vs variant dimensions. Strong, edge, local, and fractional forms change the resolving test. Diagnostic: Which object and inequality define the variant?

T6: Domain autonomy vs prime reduction. Measurement and Identifiability omit the specialist objects, constraints, and validity tests named above. Diagnostic: Would retaining only the portable parent pattern still satisfy the recognition test?

Structural–Framed Character¶

The five-criterion aggregate is 0.15 (structural). The judgment is criterion-specific:

Vocabulary travels — low (0.25). The complete vocabulary remains tied to the typed roles in the Structural Signature.
Evaluative weight — low (0.00). Application carries the stated degree of normative or interpretive judgment beyond structural recognition.
Institutional origin — low (0.25). The abstraction depends to this degree on a scholarly, technical, legal, or social convention.
Human-practice bound — low (0.00). Recognition depends to this degree on organized practice, language, measurement, or institutional action.
Import versus recognize — low (0.25). Beyond its home habitat, use of the full name increasingly becomes analogy rather than literal recognition.

The portable skeleton is a smallest set of reference points makes every object identifiable by its distance signature. The named abstraction remains structural because that skeleton alone does not supply its specialist objects, constraints, or tests.

Structural Core vs. Domain Accent¶

Structural core: A smallest set of reference points makes every object identifiable by its distance signature.

Domain accent: Connected graphs, shortest paths, landmark vertices, resolving sets, metric bases, symmetry breaking, and np-hard minimization.

Why it does not clear the prime bar: Measurement and identifiability travel; graph metric dimension is their minimum landmark-distance construction. Generalization therefore routes through parent abstractions; preserving the specialist name requires the full accent.

Measurement (prime:measurement). Shortest-path distances to selected landmarks provide the coordinates.
Identifiability (prime:identifiability). Unique distance vectors make every graph vertex distinguishable.

These are prose placement proposals only. They create no dag_edges; endpoint, redundancy, and cycle checks are recorded separately in the bundle's placement memo.

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

Not to Be Confused With¶

Locating-dominating set. a neighborhood-code set with domination. Tell: Are codes distances or adjacency neighborhoods?
Strong metric dimension. a resolving variant based on geodesic containment. Tell: Is ordinary inequality of distance vectors sufficient?
Edge metric dimension. identifying edges by distance from vertices. Tell: Are vertices or edges being resolved?
Boxicity. intersection-graph dimension by boxes. Tell: Are landmark distances involved?
Graph embedding dimension. minimum Euclidean realization dimension. Tell: Is the optimization over coordinates or landmarks?

References¶

[1] Frank Harary and Robert A. Melter, “On the Metric Dimension of a Graph”, Ars Combinatoria 2 (1976), 191–195. registry ↩a ↩b

[2] Peter J. Slater, “Leaves of Trees,” Congressus Numerantium 14 (1975), 549–559. registry ↩