Unique Vertex Identification in Graphs

31 concepts20 papers

Standard graph theory often focuses on coverage or partitioning. For example, a classic dominating set ensures that every vertex in a network is either selected or directly adjacent to a selected vertex. If you imagine these selected vertices as cell towers or smoke detectors, a dominating set guarantees that an event anywhere in the network will trigger at least one nearby sensor.

However, standard coverage is blind to identity. If a sensor fires, you know an event occurred in its immediate neighborhood, but you cannot pinpoint exactly which vertex triggered it. To achieve precise localization, the network needs a mechanism where every single vertex projects a unique structural signature.

The research direction of unique vertex identification addresses this challenge. By augmenting classical graph properties—such as domination, distance metrics, and graph coloring—with uniqueness constraints, this field provides the mathematical foundations for fault diagnosis, network monitoring, and discrete localization.

Locating-Dominating Sets and Identifying Codes

To transition from simple coverage to precise identification, we can require that the set of sensors covering a vertex uniquely identifies that vertex.

In a locating-dominating set, we select a subset of vertices $S$ such that every vertex not in $S$ has a unique combination of neighbors within $S$. If an intruder appears at an external vertex $v$, the specific collection of activated sensors in $S$ forms an unambiguous "signature" pointing directly to $v$.

Standard Domination (Blind Coverage):
[Sensor A] ------ [Node 1] ------ [Sensor B]
     \              /                  /
      \            /                  /
        -- [Node 2] ------------------
(If Sensor A and B both fire, is the target at Node 1 or Node 2? Indistinguishable.)

Locating-Domination (Unique Signatures):
[Sensor A] ------ [Node 1] ------ [Sensor B]
     \                                 /
      \                               /
        ------- [Node 2] -------------
(Node 1 is seen by A and B. Node 2 is seen only by A. Completely distinguishable.)

As Florent Foucaud et al. observe in Locating-dominating sets in twin-free graphs, this task is only possible if the graph is "twin-free"—meaning no two vertices share the exact same set of open neighborhoods. The authors established that for any twin-free graph of order $n$, a locating-dominating set requires at most $2n/3$ vertices, proving tighter bounds for specific families like split graphs.

When the sensors must also monitor themselves, the problem evolves into locating-total domination (where every node, including the sensors, must have a neighbor in the sensor set) or identifying codes (where the closed neighborhood intersection with the code uniquely identifies every vertex).

The structural limits of these configurations are governed by tight topological bounds:

A remarkable property of these systems is that standard coverage and unique identification can often be cleanly decoupled. As demonstrated by Dipayan Chakraborty et al. in A Note on Partitioning the Vertex Set of a Graph into a Dominating Set and a Locating Dominating Set, the vertex set of any graph without isolated vertices can be perfectly partitioned into two disjoint groups: one that provides standard domination and another that provides locating-domination.

Metric Dimension: Distance-Based Coordinates

What if our sensors are not limited to immediate, 1-hop neighborhoods? If a sensor can measure the exact shortest-path distance to an event, we can leverage a global coordinate system. This is the foundation of metric dimension.

In this paradigm, we select a minimal set of reference vertices called a resolving set or landmarks. Every vertex in the graph is then mapped to a coordinate vector, where each entry is the shortest-path distance to a specific landmark. If the landmarks are chosen correctly, no two vertices will share the same coordinate vector.

Landmark A (0, 2) -------- Node 1 (1, 1) -------- Landmark B (2, 0)
                            |
                            |
                         Node 2 (2, 2)

As surveyed by Richard C. Tillquist et al. in Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications, this framework acts as a discrete analogue to GPS trilateration. Instead of continuous intersecting spheres, it relies on discrete graph distances to resolve location ambiguity.

The capacity of a network to support unique addresses depends heavily on its global topology. In Bounding the Order of a Graph Using Its Diameter and Metric Dimension: A Study Through Tree Decompositions and VC Dimension, Laurent Beaudou et al. showed that while the theoretical maximum number of uniquely identifiable nodes scales exponentially with diameter and metric dimension ($n \le d^k + k$), structural constraints collapse this relationship. For tree decompositions, chordal graphs, and graphs with bounded treewidth, the maximum network size scales polynomially (often $O(kd^2)$), proving that local tree-like structures severely restrict coordinate capacity.

Neighbor-Locating Colorings

Instead of selecting a sparse subset of vertices to act as sensors, an alternative approach assigns properties globally across the entire network using graph coloring.

A standard proper coloring ensures that adjacent vertices do not share the same color. A neighbor-locating coloring adds an identification layer: every vertex within a given color class must be uniquely identifiable by the palette of colors present in its open neighborhood.

Color Class 1 (Red):
Node X (Red) ---> Neighbors contain {Blue, Green}
Node Y (Red) ---> Neighbors contain {Blue, Yellow}

Even though Node X and Node Y share the color Red, they are uniquely 
distinguished by the color palettes of their immediate neighbors.

This technique allows an external observer to identify any vertex simply by looking at its color and the colors of its neighbors. Iiro Honkala et al. proved in Locally identifying colourings for graphs with given maximum degree that any graph with a maximum degree $\Delta$ can be locally identified using at most $O(\Delta^2)$ colors, providing a constructive bound that prevents local color repetitions.

While powerful, optimizing these colorings is computationally demanding. Dipayan Chakraborty et al. demonstrated in On locating and neighbor-locating colorings of sparse graphs that finding the minimum number of colors required for neighbor-locating colorings is NP-hard, even for highly restricted sparse graph families.

This local perspective can also be applied to edge colorings. In Local rainbow colorings, Ido Ben‐Eliezer explores a framework where every vertex maintains its own edge-coloring function. The goal is to ensure that for any instance of a target subgraph, at least one vertex within that instance perceives the subgraph as a "rainbow"—meaning all its edges have completely distinct colors from that vertex's local perspective.

Why the Idea Works

Unique vertex identification works because it forces a mathematical intersection between graph topology and combinatorial uniqueness.

Whether using 1-hop neighborhoods (locating-domination), multi-hop distances (metric dimension), or local palettes (neighbor-locating colorings), the underlying mechanism remains identical: mapping the structural position of every vertex to a distinct mathematical set or vector. By understanding the boundaries of these sets, researchers can design networks that are inherently self-diagnosing and structurally transparent.

Key Foundational Work

Locally identifying colourings for graphs with given maximum degree (2012) — contributed 3 concept elements to this direction.
Local rainbow colorings (2011) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_unique_neighborhood_identification_a9c7c7d2,
  title = {unique neighborhood identification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/unique-neighborhood-identification/rdr_a9c7c7d235d14b8ebe054985dc89b86a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_unique_neighborhood_identification_a9c7c7d2_v1,
  title = {unique neighborhood identification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/unique-neighborhood-identification/rdr_a9c7c7d235d14b8ebe054985dc89b86a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}

See something wrong? Report a mistake