Currie, James; Oellermann, Ortrud R. The metric dimension and metric independence of a graph. (English) Zbl 0986.05040 J. Comb. Math. Comb. Comput. 39, 157-167 (2001). A vertex \(x\) of a graph \(G\) is said to resolve two vertices \(u\) and \(v\) of \(G\) if \(d(x,u)\neq d(x,v)\). A set \(S\) of vertices of \(G\) is a resolving set for \(G\) if every two distinct vertices of \(G\) are resolved by some vertex of \(S\). The minimum cardinality of a resolving set for \(G\) is called the metric dimension of \(G\). In this paper the problem of finding the metric dimension of a graph is formulated as an integer programming problem. It is shown how a relaxation of this problem leads to a linear programming problem and hence to a fractional version of the metric dimension of a graph. The linear programming dual of this problem is considered and the solution to the corresponding integer programming problem is called the metric independence number of the graph. Equivalently, the metric independence number of \(G\) equals the maximum cardinality of a largest collection of pairs of vertices of \(G\) no two of which are resolved by the same vertex. It is shown that the problem of deciding whether, for a given graph \(G\), the metric dimension of \(G\) equals its metric independence number is NP-complete. Trees with equal metric dimension and metric independence number are characterized. The metric independence number is established for various classes of graphs, e.g., the metric independence number of the \(n\)-cube is always 2. Reviewer: Ioan Tomescu (Bucureşti) Cited in 29 Documents MSC: 05C12 Distance in graphs 05C85 Graph algorithms (graph-theoretic aspects) 68R10 Graph theory (including graph drawing) in computer science 05C90 Applications of graph theory 90C10 Integer programming Keywords:metric dimension; metric independence; NP-completeness; integer programming; \(n\)-cube PDFBibTeX XMLCite \textit{J. Currie} and \textit{O. R. Oellermann}, J. Comb. Math. Comb. Comput. 39, 157--167 (2001; Zbl 0986.05040)