## The metric dimension and metric independence of a graph

#### View Open

#### Metadata

Afficher la notice complète#### Author

Currie, James

Oellerman, Ortrud R.

#### Date

2001#### Citation

Currie, James, and Ortrud R. Oellerman, "The metric dimension and metric independence of a graph," Journal of Combinatorial Mathematics and Combinatorial Computing 39 (2001): 157–167.

#### Abstract

A vertex x of a graph G resolves two vertices u and v of G if the
distance from x to u does not equal the distance from x to 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. The problem of
nding the metric dimension of a graph is formulated as an integer pro-
gramming 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 of the graph.
It is shown that the problem of deciding whether, for a given graph
G, the metric dimension of G equals its metric independence is NP-
complete. Trees with equal metric dimension and metric independence
are characterized. The metric independence number is established for
various classes of graphs.