Metric representations by minimal graphs

A resolving set in a graph G is a vertex subset 𝑊 = { 𝜔 1 , … , 𝜔 𝑛 } ⊆ 𝑉 ⁡ ( 𝐺 ) such that each 𝑢 ∈ 𝑉 ⁡ ( 𝐺 ) can be uniquely identified by the vector 𝑟 ⁡ ( 𝑢 | 𝑊 ) = ( 𝑑 ⁡ ( 𝑢 , 𝜔 1 ) , … , 𝑑 ⁡ ( 𝑢 , 𝜔 𝑛 ) ) of metric coordinates of u with respect to W . The reverse problem of identifying the vector sets that are the sets of coordinates of some graph provides the concept of realizable vector set 𝑆 ⊂ ℤ 𝑛 by a pair ( 𝐺 , 𝑊 ) , where W is a resolving set of the graph G , that means that 𝑆 = { 𝑟 ⁡ ( 𝑢 | 𝑊 ) : 𝑢 ∈ 𝑉 ⁡ ( 𝐺 ) } . We here focus on the minimality of the realizations of vector sets, with respect to their edge sets. On the one hand, we study conditions under which it is possible to remove an edge from the graph and keep the realizability condition. This will allow us to characterize uniquely realizable vector sets. On the other hand, we prove that the decision problem of realizing a vector set by a graph with a given number of edges is a NP-hard problem. Finally, we characterize the vector sets that are realizable by a tree and also the case in which such a realization is the unique one.