Link dimension and exact construction of graphs from distance vectors

• Published in: Discrete Applied Mathematics 2022-03, Vol.309, p.160-171
• Main Authors: Mahindre, Gunjan S., Jayasumana, Anura P.
• Format: Article
• Language: English
• Subjects: Edge; Graph reconstruction; Graphability; Inverse problems; Landmark; Metric dimension; Nodes; Resolution set
• ISSN: 0166-218X; 1872-6771
• DOI: 10.1016/j.dam.2021.11.013

Minimum resolution set and associated metric dimension provide the basis for unique and systematic labeling of nodes of a graph (G) using distances to a set of landmarks. Such a distance vector set, however, may not uniquely identify the graph or allow for its exact construction. The concept of construction set is presented, which overcomes these limitations. Link dimension (ξ(G)) is the minimum cardinality of a construction set. We study ambiguity in the given distance vector set and conditions for resolving them. Bounds over link dimension, proofs for link dimension for various graph families and relationship between graph dimensions and graph spectra are presented. The inverse problem of identifying whether a given set of non-negative distance vectors can be associated with a graph is also addressed, introducing the concept of graphability of distance vectors. A graph of N nodes can now be compressed to a representation with an N×ξ(G) matrix which allows for its exact reconstruction. •A graph dimension that goes beyond unique labeling to capturing complete topology.•Overcomes ambiguity in reconstructing a graph from its resolution set.•A unique way to represent a graph with a compact matrix.•Conditions for a given distance vector set to be graphable.•Conditions for a given distance vector set to correspond to a resolution set.