remarkRemark hypothesisHypothesis claimClaim A Survey of Metric Dimension and
its ApplicationsRichard C. Tillquist, Rafael M. Frongillo, Manuel E. Lladser

# Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension
and its Applications††thanks: Submitted to the editors 4/1/2021. This article
was partially funded by NSF IIS grant 1836914.

Richard C. Tillquist Department of Computer Science, University of Colorado,
Boulder, The United States<EMAIL_ADDRESS><EMAIL_ADDRESS>Rafael M. Frongillo22footnotemark: 2 Manuel E. Lladser
Department of Applied Mathematics, University of Colorado, Boulder, The United
States<EMAIL_ADDRESS>
###### Abstract

The metric dimension of a graph is the smallest number of nodes required to
identify all other nodes based on shortest path distances uniquely.
Applications of metric dimension include discovering the source of a spread in
a network, canonically labeling graphs, and embedding symbolic data in low-
dimensional Euclidean spaces. This survey gives a self-contained introduction
to metric dimension and an overview of the quintessential results and
applications. We discuss methods for approximating the metric dimension of
general graphs, and specific bounds and asymptotic behavior for deterministic
and random families of graphs. We conclude with related concepts and
directions for future work.

###### keywords:

Metric dimension, graph embedding, multilateration, graph isomorphism,
resolving set

05C12, 05C60, 05C62, 05C85, 05C90, 68R10

###### Contents

  1. 1 Introduction
  2. 2 Formal Definition
    1. 2.1 Simple Examples
      1. 3 Computational Complexity and Approximation
        1. 3.1 NP-Completeness
        2. 3.2 Information Content Heuristic
        3. 3.3 Other Heuristics
          1. 4 Graph Features and Metric Dimension Relationships
            1. 4.1 Diameter and Metric Dimension
            2. 4.2 Twin Nodes and Metric Dimension
            3. 4.3 Graphs with Extreme Metric Dimension
              1. 5 Specific Families of Graphs
                1. 5.1 Fans and Wheels
                2. 5.2 Trees and Unicyclic Graphs
      2. 5.3 Grids, Honeycombs, and Hexagon Networks
        1. 5.4 Hamming Graphs
          1. 6 Random Graph Models
            1. 6.1 Erdös-Rényi Random Graphs
            2. 6.2 Stochastic Block Model
            3. 6.3 Random Trees and Forests
              1. 7 Applications
                1. 7.1 Source Localization
                2. 7.2 Detecting Network Motifs
                3. 7.3 Embedding Biological Sequence Data
                  1. 8 Related Concepts
                    1. 8.1 Doubly Resolving Sets
                    2. 8.2 Strong Metric Dimension
                    3. 8.3 Multilateration
                    4. 8.4 Truncated Metric Dimension
                    5. 8.5 Resolving Number, Upper Dimension, Random $k$-dimensionality
                      1. 9 Conclusion

##  1 Introduction

In the Euclidean plane, any set of three non-collinear points is enough to
uniquely distinguish all points in the space based on distances. This process,
called trilateration in $\mathbb{R}^{2}$, is the basic technique through which
Global Positioning Systems (GPS) are able to pinpoint a location on the
surface of the Earth. More generally, if $\|\cdot\|$ denotes the Euclidean
distance and
$R=\\{\mathbf{r}_{1},\ldots,\mathbf{r}_{n+1}\\}\subset\mathbb{R}^{n}$ is a set
of $n+1$ affinely independent points, the vectors
$(\lVert\mathbf{x}-\mathbf{r}_{1}\rVert,\dots,\lVert\mathbf{x}-\mathbf{r}_{n+1}\rVert)$
and
$(\lVert\mathbf{y}-\mathbf{r}_{1}\rVert,\dots,\lVert\mathbf{y}-\mathbf{r}_{n+1}\rVert)$
for $\mathbf{x},\mathbf{y}\in\mathbb{R}^{n}$ are different when
$\mathbf{x}\neq\mathbf{y}$.

The situation becomes more complex, however, if the space of interest is
discrete instead of continuous. One class of discrete spaces of particular
interest are those which can be represented as graphs coupled with shortest
path distance. On a graph $G=(V,E)$ the notion of _metric dimension_ is
analogous to the number of satellites required for GPS to work effectively.
The goal is to pick a small set of vertices $R\subseteq V$ capable of
identifying every vertex based solely on shortest path distances to $R$.
Solving this problem exactly is computationally complex but provides
information useful in a variety of settings. A small set of “satellites” or
“landmarks” in a discrete space can be valuable in assisting robots navigating
over a physical space or in tracking the progress of a disease as it spreads
between cities. It could also be used in more abstract settings like
identifying a source of misinformation in a social network, comparing network
structure, categorizing chemical structures, or representing symbolic data
numerically.

In this work we collate and interpret a number of theoretical results and
approximation techniques associated with metric dimension, paying particular
attention to specific types of graphs and applications. We survey recent work
and describe promising directions for future work.

##  2 Formal Definition

Let $G=(V,E)$ be a graph, potentially with weighted edges, multi-edges, and
self loops, and let $d(u,v)$ denote the shortest path distance in $G$ from
$u\in V$ to $v\in V$.

######  Definition 2.1.

(Resolving Set.) $R\subseteq V$ is resolving if, for all distinct $u,v\in V$,
there exists $r\in R$ such that $d(r,u)\neq d(r,v)$. Such an $r$ is said to
resolve or distinguish $u$ and $v$.

In the context of $\mathbb{R}^{n}$, any set of $(n+1)$ or more affinely
dependent points is analogous to a resolving set in a graph.

By definition, $R=\\{v_{1},\ldots,v_{k}\\}$ is resolving if and only if the
transformation

$d(u|R):=\big{(}d(r_{1},u),\dots,d(r_{k},u)\big{)}$

from $V$ to $\mathbb{R}^{|R|}$ is injective, i.e., every vertex $u\in V$ is
uniquely represented by the vector of distances from all vertices in $R$
(listed in an arbitrary but specified order) to $u$. In many settings,
minimizing the dimension $|R|$ of these vectors is a central goal.

######  Definition 2.2.

(Metric Dimension.) The metric dimension $\beta(G)$ of $G$ is the smallest
size of resolving sets on $G$. If $R$ is a resolving set on $G$ and
$|R|=\beta(G)$, $R$ is called a minimal resolving, basis, or reference set of
$G$.

In the context of graphs, the concept of metric dimension was introduced
separately by Slater in 1975 [102] and by Harary and Melter in 1976 [48],
though the dimension of graphs was discussed earlier by Erdös et al. in 1965
[31]. Both the Slater and Harary and Melter papers focus on the metric
dimension of trees and describe equivalent exact formula for graphs of this
kind. Harary and Melter briefly discuss the metric dimension of several other
types of graphs including cycles, complete graphs, and complete bipartite
graphs though the metric dimension of wheel graphs is incorrectly stated as
two. They also give an algorithm to reconstruct a tree given distances from
every node to the elements of a resolving set. This is not possible for
general graphs as not all edges are guaranteed to be represented in a shortest
path with an element of a resolving set as an endpoint (Section 8.2).

###  2.1 Simple Examples

Before continuing, we examine several types of graphs for which minimal
resolving sets are readily described and easily visualized. Through this
examination, we hope to strengthen the reader’s intuitive grasp of metric
dimension and to solidify concepts that are important in future sections.

For $G=(V,E)$ connected with $|V|=n\geq 2$, the path graph $P_{n}$, and the
complete graph $K_{n}$ represent the two extremes of metric dimension. Indeed,
$\beta(G)=1$ if and only if $G=P_{n}$, and $\beta(G)=n-1$ if and only if
$G=K_{n}$ [15]. Resolving sets for $P_{n}$ and $K_{n}$ are readily apparent
(see Section 2.1). For a path, either of the end vertices resolves every
vertex, as each distance 0 to $(n-1)$ is attained exactly once. For a complete
graph, every vertex is at distance 0 from itself and at distance 1 from all
other vertices. This means that a single vertex $v\in V$ uniquely identifies
itself but no other vertices. In order to distinguish all vertices, a
resolving set of $K_{n}$ must be of size at least $(n-1)$. Moreover, any such
set is resolving because the excluded vertex is the only one at a strictly
positive distance from all other vertices.

& $(0)$$(1)$$(2)$$(3)$$(4)$ $(0,1)$$(1,0)$$(2,1)$$(2,2)$$(1,2)$
(2,0)(3,1)(4,2)(5,3)(1,1)(2,2)(3,3)(4,4)(0,2)(1,3)(2,4)(3,5)

Figure 1: Minimal resolving sets (in red) for the complete graph $K_{5}$
(upper left), the path $P_{5}$ (upper right), the cycle $C_{5}$ (lower left),
and the grid $G_{4,3}$ (lower right). Nodes are annotated with their distance
vectors $d(u|R)$, which are all unique.

The cycle graph $C_{n}$ on $n>2$ vertices has metric dimension 2 [16]. No
single vertex set can resolve $C_{n}$ because every vertex has degree 2. Next,
we construct a set of size 2 and show that it is resolving. Suppose that the
vertex set of $C_{n}$ is $\\{0,\ldots,n-1\\}$, where consecutive integers are
neighbors and so are $0$ and $n-1$. Let $R=\\{0,1\\}$. Then
$d(x|R)=(\min\\{x,n-x\\},\min\\{x-1,n+1-x\\})$. But using that
$\min\\{a,b\\}=(a+b-|a-b|)/2$, it follows that if $d(x|R)=d(y|R)$ then
$|n-2x|=|n-2y|$ and $|n-2(x-1)|=|n-2(y-1)|$; in particular, $x$ and $y$ are at
the same distance from $n/2$, and so are $x-1$ and $y-1$, which is possible
only when $x=y$. Hence, $\beta(C_{n})=2$ (Section 2.1).

Finally, consider the two-dimensional grid $G_{m,n}$ with dimensions $m,n\geq
1$. The vertices of this graph correspond to ordered pairs
$(x,y)\in\mathbb{Z}^{2}$ such that $0\leq x<m$ and $0\leq y<n$. The edges
correspond to pairs at Euclidean distance exactly 1, when considered as points
in $\mathbb{R}^{2}$ (see Section 2.1). In particular, every vertex has degree
at least two and no singleton can be resolving. Clearly, $d((0,0),(x,y))=x+y$
and, more generally, $d((u,v),(x,y))=|u-x|+|v-y|$. Thus, shortest path
distance in this case is equivalent to the $\ell_{1}$ norm or Manhattan
distance. Let $R=\\{(0,0),(0,n-1)\\}$. Observe that
$d((a,b)|R)=(a+b,a+n-1-b)$. Then, for vertices $(a,b)$ and $(x,y)$, we have
$d((a,b)|R)=d((x,y)|R)$ if and only if $a=x$ and $b=y$. Hence,
$\beta(G_{m,n})=2$ [66, 82]. A symmetric argument shows that
$R=\\{(0,0),(m-1,0)\\}$ is also resolving for $G_{m,n}$.

##  3 Computational Complexity and Approximation

Verifying that a given set of nodes $R$ in $G=(V,E)$ constitutes a resolving
set is straightforward. For every $v\in V$, the vector of distances $d(v|R)$
can be generated in $O(|E|+|V|\log|V|)$ time. This collection of
$\binom{|V|}{2}$ vectors then needs to be checked for duplicates. If all
vectors are unique, the set is resolving, otherwise there is at least one pair
of indistinguishable nodes in $G$ based on $R$.

A brute force solution determining the exact metric dimension of a general
graph, on the other hand, requires an exhaustive search over a very large
solution space. For a fixed set of size $s$, there are $\binom{|V|}{s}$
subsets of nodes that must be considered. Since we are interested in the
smallest $s$ for which a subset of nodes of this size resolves $G$, increasing
values of $s$ starting at 1 must be tested until a solution is found. Indeed,
for a positive integer $k$, deciding whether $\beta(G)\leq k$ is an NP-
complete problem. As a result, several approximation methods designed to find
small resolving sets on general graphs have been developed.

In what remains of this section we discuss one approach used to show the NP-
completeness of the metric dimension problem, we describe an approximation
algorithm based on a greedy selection criterion [50], and we outline two
heuristic search techniques that have been applied to the problem of quickly
finding small resolving sets.

###  3.1 NP-Completeness

The decision problem associated with metric dimension is to determine, given a
graph $G$ and integer $k$, whether or not $\beta(G)\leq k$. This decision
problem is NP-complete, i.e., computationally intractable. (For background on
computational complexity, see, e.g., Goldreich [41].) In this section, we
present one proof of NP-completeness via reduction from 3-SAT, the problem of
testing whether a given Boolean formula in conjunctive normal form, with three
literals per clause, has a satisfying assignment [64]. A reduction from the
3-dimensional matching problem to metric dimension is cited in [39], though we
have not been able to find this proof in the literature.

Formally, the 3-SAT problem is as follows. Let $E$ be a Boolean expression in
conjunctive normal form with $n$ variables $x_{1},\dots,x_{n}$ and $m$ clauses
$C_{1},\dots,C_{m}$. For instance, the formula $(x_{1}\vee\overline{x_{2}}\vee
x_{3})\wedge(x_{2}\vee x_{3}\vee\overline{x_{4}})$ consists of two clauses and
four variables. 3-SAT is the problem of determining, given such a formula $E$,
whether there exists an assignment mapping variables to truth values making
$E$ true. For the previous formula, setting $x_{1}$ and $x_{2}$ to True and
$x_{3}$ and $x_{4}$ to False is one such an assignment.

For an arbitrary 3-SAT instance $E$ we will construct a graph $G$ such that
$E$ is satisfiable if and only if $\beta(G)=n+m$. We follow the construction
of [66]. For every variable $x_{i}$ create a six cycle with nodes labeled
$T_{i}$, $a^{1}_{i}$, $b^{1}_{i}$, $F_{i}$, $b^{2}_{i}$, and $a^{2}_{i}$,
listed clockwise (see Fig. 2 left). For every clause $C_{j}$ create a four
star with nodes labeled $c^{k}_{j}$, with $1\leq k\leq 5$, and central node
$c^{2}_{j}$ (see Fig. 2 right).

These cycles and stars are used to form a connected graph by including the
edge $\\{T_{i},c^{1}_{j}\\}$ for every variable $x_{i}$ and every clause
$C_{j}$. In addition, when $x_{i}$ is used as a positive literal in $C_{j}$,
the edges $\\{F_{i},c^{1}_{j}\\}$ and $\\{F_{i},c^{3}_{j}\\}$ are added to the
graph. Instead, when $x_{i}$ is used as a negative literal in $C_{j}$ the
edges $\\{F_{i},c^{1}_{j}\\}$ and $\\{T_{i},c^{3}_{j}\\}$ are added.
Otherwise, if $x_{i}$ does not appear in $C_{j}$ the edges
$\\{F_{i},c^{1}_{j}\\}$, $\\{F_{i},c^{3}_{j}\\}$, and $\\{T_{i},c^{3}_{j}\\}$
are added. (See Fig. 3.) Since there are a total of $6n+5m$ nodes in the final
graph, and there are at most four edges between the subgraphs representing
$x_{i}$ and $C_{j}$ for all $1\leq i\leq n$ and $1\leq j\leq m$, this
construction takes polynomial time.

Notice that any resolving set $R$ of $G$ must include at least one of
$\\{a^{1}_{i},a^{2}_{i},b^{1}_{i},b^{2}_{i}\\}$ for all $1\leq i\leq n$ and at
least one of $\\{c^{4}_{j},c^{5}_{j}\\}$ for all $1\leq j\leq m$. Hence
$\beta(G)\geq n+m$. Showing that $\beta(G)=n+m$ if $E$ is satisfiable is
straightforward. Given an assignment of the variables to true or false, take
$R=\\{c^{4}_{j}\mid 1\leq j\leq m\\}\cup\\{a^{1}_{i}\mid x_{i}\text{ is
true}\\}\cup\\{b^{1}_{i}\mid x_{i}\text{ is false}\\}$. (One could also choose
$c^{5}_{j}$, $a^{2}_{i}$, and/or $b^{2}_{i}$).

To see that $R$ is resolving, first consider the variable gadget for $x_{i}$,
and any clause $C_{j}$. Recall that $c^{4}_{j}\in R$. The vertices of the
$x_{i}$ gadget are split into two groups based on distances to $c^{4}_{j}$:
vertices $\\{T_{i},F_{i}\\}$ at distance 3 and
$\\{a^{1}_{i},a^{2}_{i},b^{1}_{i},b^{2}_{i}\\}$ at distance 4. Any vertex in
the set $\\{a^{1}_{i},a^{2}_{i},b^{1}_{i},b^{2}_{i}\\}$, therefore, serves to
disambiguate the elements of these groups: $T_{i}$ and $F_{i}$ will have
distance 1 and 2, or vice versa, and the remaining nodes will attain every
distance in $\\{0,1,2,3\\}$. As we have either $a^{1}_{i}\in R$ or
$b^{1}_{i}\in R$, the variable gadget is resolved. In fact, this statement
holds regardless of whether the formula is satisfiable.

Now consider a clause $C_{j}$ and a variable $x_{i}$ that causes this clause
to be satisfied. There are two cases: either $x_{i}$ is a positive literal in
$C_{j}$ and is given a value of true, or $x_{i}$ is a negative literal in
$C_{j}$ and is given a value of false. In the first case, we have
$a^{1}_{i}\in R$, and recall $c^{4}_{j}\in R$. In the $C_{j}$ gadget,
$c^{2}_{j}$ is the unique vertex at distance 1 from $c^{4}_{j}$, and
$c^{5}_{j}$ is the unique vertex at distance 4 from $a^{1}_{i}$,
distinguishing these vertices from all others. Finally, we have
$d(a^{1}_{i},c^{1}_{j})=2$ and $d(a^{1}_{i},c^{3}_{j})=3$, finishing the proof
of the first case. The second case is symmetric to the first, with the edge
$\\{F_{i},c^{3}_{j}\\}$ becoming $\\{T_{i},c^{3}_{j}\\}$, and the role of
$a^{1}_{i}$ played by $b^{1}_{i}$ instead.

Conversely, it can be shown that $E$ is satisfiable if $\beta(G)=n+m$ by
setting $x_{i}$ to true if either $a^{1}_{i}$ or $a^{2}_{i}$ is in the
resolving set and to false otherwise. Thus, this construction reduces 3-SAT to
the metric dimension decision problem in polynomial time.

$T_{i}$$a_{i}^{1}$$a_{i}^{2}$$b_{i}^{1}$$b_{i}^{2}$$F_{i}$

$c_{j}^{1}$$c_{j}^{2}$$c_{j}^{3}$$c_{j}^{4}$$c_{j}^{5}$

Figure 2: Visualization of gadgets [66] for a single variable (left) and a
single clause (right) in a Boolean expression. $x_{1}$$x_{2}$$x_{3}$$x_{4}$
Figure 3: The graph produced by the reduction for the formula
$E=(x_{1}\vee\overline{x_{2}}\vee x_{3})\wedge(x_{2}\vee
x_{3}\vee\overline{x_{4}})$. Gadgets for variables and clauses are oriented as
in Figure 2. As $E$ is satisfiable, the graph has a resolving set of size
$4+2=6$, shown in red.

Although metric dimension is a computationally difficult problem on arbitrary
graphs, there are efficient and fixed-parameter tractable algorithms in
certain restricted settings. Indeed, trees [48, 102], cographs [30], and
outerplanar graphs [27] admit linear or polynomial time algorithms, and
interval [38] and permutation graphs [7] have fixed-parameter tractable
algorithms with respect to resolving set size. There are also fixed-parameter
tractable algorithms for metric dimension on general graphs with respect to
other graph quantities including vertex cover [49], maximum leaf number [29],
and modular width [7].

###  3.2 Information Content Heuristic

Approximate solutions to the metric dimension problem on general graphs may be
generated using a fairly simple greedy algorithm. Originally devised for use
on instances of the test set problem [8] and later modified for estimating the
metric dimension of graphs [50], this algorithm is based on an Information
Content Heuristic (ICH).

The underlying concept is similar to information gain as it relates to the
construction of decision trees [91]. Let $G=(V,E)$ be a graph with $n=|V|$.
Consider the classification problem for which each vertex is a training
example from a unique class. The feature vector of each $v\in V$ is simply
$d(v|V)\in\mathbb{R}^{n}$, the shortest path distances to all vertices in the
graph. In particular, the $(n\times n)$ distance matrix $\mathbf{D}$
associated with $G$ fully describes the training data. The choice of resolving
set $R$ can thus be thought of as the choice of some subset of features:
$d(v|R)$ is simply a selection of entries of $d(v|V)$ corresponding to the
“features” $R$.

In the usual greedy algorithm to construct a decision tree, at each node of
the decision tree, one selects the feature which maximizes the information
gained about the true class at the child nodes. In the case of resolving sets,
each node of the decision tree corresponds to the addition of some vertex $u$
to $R$, with branches corresponding to the possible values of $d(\cdot,u)$. To
measure information in our setting, consider the distribution $p_{R}$ induced
by the equivalence classes of $d(\cdot|R)$, which assigns probability
$|\\{v\in V:d(v|R)=d\\}|/n$ to each possible value $d\in\\{d(v|R):v\in V\\}$.
Then the information of $R$ is measured by the Shannon entropy of $p_{R}$,
denoted $H(R)$. Letting $R_{t}$ be the resolving set at iteration $t$, with
$R_{0}=\emptyset$, the ICH algorithm therefore chooses the vertex $v_{t}\in V$
to maximize $H(R_{t}\cup\\{v_{t}\\})$. The algorithm terminates when
$H(R_{t})=\log n$, the maximum possible entropy over $n$ items, indicating
that all $n$ vertices are uniquely represented by their distances to
$R_{t}$.111In fact, the ICH algorithm is exactly the same as the information
gain algorithm for decision trees, under the constraint that the decision made
at every node of the tree at the same level must be the same, i.e., we choose
the same vertex at iteration $t$ for all decision nodes at level $t-1$. To see
the equivalence, let $n_{d}=|\\{v\in V:d(v|R)=d\\}|$ be the size of
equivalence class $d$, and $p_{d}$ be the distribution of labels within
equivalence class $d$, i.e., the unform distribution on all $n_{d}$ vertices
in the equivalence class. Then maximizing information gain, weighted by the
size of each decision node (recall that we must choose the same feature to
split at all nodes), is the same as maximizing $H(p_{R})$:
$\min\sum_{d}\frac{1}{n_{d}}H(p_{d})=\min\sum_{d}\frac{1}{n_{d}}\log(n_{d})=\max-\sum_{d}\frac{1}{n_{d}}\log(\frac{1}{n_{d}})=\max
H(p_{d})$.

Asymptotically, the time complexity of the ICH algorithm is $O(n^{3})$. This
makes it an effective algorithm only for approximating the metric dimension of
relatively small graphs. Nevertheless, this algorithm does have the
significant advantage of guaranteeing a $1+(1+o(1))\cdot\ln(n)$ approximation
ratio (i.e., the approximate metric dimension of a graph discovered by the ICH
is never more than $1+(1+o(1))\cdot\ln(n)$ times as large as its true metric
dimension). This is the best possible approximation ratio for the metric
dimension problem [50].

###  3.3 Other Heuristics

Among many heuristic methods commonly deployed in non-convex search problems,
genetic algorithms and variable neighborhood search in particular have been
used to find small resolving sets on general graphs with some success. Genetic
algorithms, inspired by the concept of biological evolution, seek optimal
solutions to problems by incrementally changing a population of candidate
solutions from one generation to the next through the biologically motivated
operations of mutation and selective recombination [26]. This approach has
been shown to perform quite well when applied to metric dimension in
comparison to other state-of-the-art algorithms, including methods based on an
integer programming formulation of the problem and the CPLEX [23] optimization
package [69].

The variable neighborhood search (VNS) technique starts with an initial, non-
optimal solution and iteratively expands a neighborhood on which to perform a
local search. When a point in the space which improves upon the initial
solution is found, the search is restarted with this point at its center. In
the context of searching for small resolving sets, VNS seems to outperform
genetic algorithm based methods on many kinds of graphs and has been used to
improve upon previous upper bounds for certain hypercubes [85].

##  4 Graph Features and Metric Dimension Relationships

In this section, we overview some general observations about metric dimension
and its relationship to other graph quantities. These observations are often
useful in bounding or exactly determining the metric dimension of a given
graph.

###  4.1 Diameter and Metric Dimension

The diameter of a graph $G=(V,E)$, denoted $\mathrm{diam}(G)$, is the length
of a longest shortest path in $G$. For ease of notation, let
$\delta=\mathrm{diam}(G)$ and $k=\beta(G)$. It is not surprising that a
relationship exists between $\delta$ and $k$. Indeed, let $R\subset V$ be a
minimum resolving set of $G$ and consider $d(v|R)$ for each $v\in V$. Since
such vectors can only contain a 0 when $v\in R$ and, for $v\notin R$, $1\leq
d(r,v)\leq\delta$, it follows that $|V|\leq\delta^{k}+k$ [66]. This bound is
usually loose, though graphs with $|V|=\delta+k$ have been fully characterized
[52]. The related bound,

$n\leq(\lfloor
2\delta/3\rfloor+1)^{k}+k\sum_{i=1}^{\lceil\delta/3\rceil}(2i-1)^{k-1},$

is generally tighter [52]. This bound can be made tighter still for specific
families of graphs. We list a few results here [6].

  * •

If $G$ is a tree, $|V|\leq(\delta k+4)(\delta+2)/8$, with equality for trees
with even diameter [6].

  * •

If $G$ is an outerplanar graph, $|V|=O(\delta^{2}k)$ [6].

  * •

If $K_{i}$ is not a minor of $G$, $|V|\leq(\delta k+1)^{i-1}+1$ [6].

  * •

If $G$ has constant treewidth, $|V|=O(k\delta^{O(1)})$ [6].

  * •

If the rankwidth of $G$ is at most $r$, $|V|\leq(\delta
k+1)^{\delta(3(2^{r})+2)}+1$ [6].

  * •

If $G$ is an interval or permutation graph, $|V|=O(\delta k^{2})$ [37].

  * •

If $G$ is a unit interval graph, $|V|=O(\delta k)$ [37].

###  4.2 Twin Nodes and Metric Dimension

Let $G=(V,E)$ be an undirected graph and, for each $v\in V$, define the
closed-neighborhood of $v$ as $N(v)=\\{u\mid\\{u,v\\}\in E\\}$. We call
$u,v\in V$ twins when $N(u)\cup\\{u\\}=N(v)\cup\\{v\\}$.

Twin nodes have an interesting relationship to metric dimension. In fact, when
$u$ and $v$ are twins, $d(u,w)=d(v,w)$, for all $w\in V\setminus\\{u,v\\}$. As
a result, any resolving set of $G$, minimal or not, must include at least one
of $u$ and $v$. More formally, define over $V$ the equivalence relation:
$u\equiv v$ if and only if $u$ and $v$ are twins. Let $\tau(G)$ be the set of
twin equivalence classes of $G$. Then, if $R$ is a resolving set of $G$,
$|R\cap\tau|\geq|\tau|-1$, for each $\tau\in\tau(G)$. In particular [52]:

$\beta(G)\geq\sum_{\tau\in\tau(G)}(|\tau|-1).$

Twin nodes have been used, for example, to study connections between metric
dimension, diameter, and graph size [52].

###  4.3 Graphs with Extreme Metric Dimension

As we saw in Section 2.1, for $G=(V,E)$, $1\leq\beta(G)\leq n-1$, where
$\beta(G)=1$ if and only if $G\cong P_{n}$, and $\beta(G)=n-1$ if and only if
$G\cong K_{n}$. In fact, for every $1\leq k\leq n-1$ there is a connected
graph $G$ with $n$ vertices and $\beta(G)=k$ [15]. Suppose $G=(V,E)$ such that
$\beta(G)=2$. Such graphs have not been fully characterized but there are a
set of simple properties that they must have [66]. In particular, if
$\\{u,v\\}\subset V$ is a resolving set of $G$ of minimum size:

  1. 1.

$G$ cannot contain $K_{5}$ as a subgraph.

  2. 2.

$G$ cannot contain $K_{3,3}$ as a subgraph. ($K_{m,n}$ denotes the complete
bipartite graph with partitions of size $m$ and $n$.)

  3. 3.

There is a unique shortest path between $u$ and $v$.

  4. 4.

$\deg(w)\leq 5$ for all nodes $w\in V$ on the shortest path between $u$ and
$v$.

  5. 5.

$\deg(u)\leq 3$ and $\deg(v)\leq 3$.

Properties $(1)$ and $(2)$ may bring Wagner’s theorem [113] to mind, a
characterization of planar graphs forbidding $K_{5}$ and $K_{3,3}$ as minors,
suggesting that $G$ must be planar. On the contrary, there are non-planar
graphs with metric dimension 2 [66].

Graphs $G=(V,E)$ with $\beta(G)=(n-2)$, on the other hand, have been fully
characterized [15]. For two graphs $G_{1}$ and $G_{2}$, let $G_{1}\cup G_{2}$
denote their disjoint union, and let $G_{1}+G_{2}$ denote the graph formed by
taking a disjoint union and joining every node in $G_{1}$ with every node in
$G_{2}$. Furthermore, define $\overline{K}_{n}$ to be a graph with $n$ nodes
and no edges. Then the metric dimension of a graph with $n$ nodes is $n-2$ if
and only if the graph is one of the following:

  * •

A complete bipartite graph, $K_{s,t}$ with $s,t\geq 1$.

  * •

$K_{s}+\overline{K}_{t}$ with $s\geq 1$ and $t\geq 2$.

  * •

$K_{s}+(K_{1}\cup K_{t})$ with $s,t\geq 1$.

These characterizations of graphs with large and small metric dimension, along
with relationships to other graph quantities like total twin nodes and
diameter, are often useful when beginning the search for the metric dimension
of specific kinds of graphs.

##  5 Specific Families of Graphs

While determining the metric dimension of arbitrary graphs is a
computationally complex task, exact formulae, upper bounds, and polynomial
time algorithms exist for certain types of graphs. In practical applications
these analytic and algorithmic results are of crucial importance. Generic
approximation algorithms tend to provide small resolving sets but do not scale
well enough with network size to be useful on larger networks which routinely
include more than $10^{6}$ total nodes [14, 83, 108]. Tailored algorithms for
specific graph structures can therefore be useful in quickly discovering small
resolving sets even on large networks.

In what follows, we discuss some of the more prominent graph families on which
metric dimension has been studied. Tables 2 to 5 provide a short, incomplete
list of known bounds with references. The literature also addresses Cartesian
products of graphs [12, 61] and infinite graphs [11], which we do not discuss.

###  5.1 Fans and Wheels

Recall the path $P_{n}$ and cycle $C_{n}$ from Section 2.1, two of the
simplest graphs to study metric dimension. Fans and wheels are simple
modifications of these which add a new fully-connected vertex. Formally, the
fan graph on $n+1$ vertices, denoted $F_{n}$, consists of a path $P_{n}$ on
$n$ vertices and one additional vertex, $a$, adjacent to all vertices on
$P_{n}$. Similarly, the wheel graph $W_{n}$ is a cycle $C_{n}$ of size $n$
with an additional vertex, $a$, adjacent to all vertices on $C_{n}$. As the
metric dimensions of graphs $P_{n}$ and $C_{n}$ are elementary to determine (1
and 2, respectively), one might expect the metric dimensions of $F_{n}$ and
$W_{n}$ to be similarly trivial. Yet despite their simplicity, fans and wheels
have much more complex expressions for their metric dimension. Part of this
complexity stems from the diameter of these graphs shrinking from order $n$ to
at most 2, reducing the possible shortest path distances to the range
$\\{0,1,2\\}$. Specifically, their metric dimensions are given as follows
[99].

(1) $\beta(F_{x+5k})=\beta(W_{x+5k})=\begin{cases}3+2k,&\text{ when
}x\in\\{7,8\\},\\\ 4+2k,&\text{ when }x\in\\{9,10,11\\},\end{cases}$

for all $k\geq 0$. We find instructive to provide a high level proof of this
result. Accordingly, we assume in what follows that $n>6$.

Focusing first on $F_{n}$, observe that $a$ appears in none of its minimal
resolving sets. To see this, suppose for a contradiction that $R$ is a minimal
resolving set of $F_{n}$ such that $a\in R$. Since $R$ is minimal, there must
be two vertices $u,v\in V$ with
$d(u|R\setminus\\{a\\})=d(v|R\setminus\\{a\\})$. Furthermore, without loss of
generality we must have $u=a$, since otherwise $d(u,a)=d(v,a)=1$ and $R$ would
not resolve $u$ and $v$. Thus, as $u=a$, and as $d(a,R\setminus\\{a\\})$ is
the all-ones vector, $v$ must be distance 1 from every node in
$R\setminus\\{a\\}$. By definition of $F_{n}$, there are at most two nodes
other than $a$ at distance 1 from $v$, so $|R\setminus\\{a\\}|\leq 2$. One can
check that there are now only 6 possible values of
$d(\cdot|R\setminus\\{a\\})$, namely
$(1,2),(0,2),(1,1),(2,0),(2,0),(2,1),(2,2)$. As $a$ is at distance 1 from all
nodes on the path, and $n>6$ we cannot have resolved $F_{n}$. Hence, no
minimal resolving set of $F_{n}$ contains the vertex $a$.

Let $R$ be a minimal resolving set of $F_{n}$ of size $\beta$. Note that at
most one vertex of $P_{n}$ can be at distance 2 from all vertices in $R$.
Besides, at most $\beta$ vertices of $P_{n}$ can be adjacent to exactly one
vertex of $R$. Otherwise, if there were more, the pigeonhole principle would
imply that that at least two vertices are adjacent to the same vertex of $R$
and, therefore, would be indistinguishable. As a result, all the remaining
nodes of $P_{n}$ must either be in $R$, or be adjacent to exactly two vertices
of $R$. Note that having fewer than $\beta$ vertices adjacent to a single
element of $R$ cannot increase the overall number of vertices resolved. Hence
$n\leq 1+2\beta+\beta/2$, or equivalently: $\lceil 2(n-1)/5\rceil\leq\beta$.
But, because $n>6$, we may write $n=x+5k$ with $7\leq x\leq 11$ and $k\geq 0$.
In particular [99]:

$\beta(F_{x+5k})\geq\begin{cases}3+2k,&\text{ when }x\in\\{7,8\\};\\\
4+2k,&\text{ when }x\in\\{9,10,11\\}.\end{cases}$

Furthermore, it is easy to see that this lower bound on $\beta(F_{x+5k})$ is
also an upper bound via a simple construction. In particular, there is a
resolving set of $F_{x+5k}$ of size $3+2k$ when $x$ is 7 or 8 and of size
$4+2k$ when $x$ is 9, 10, or 11. Let $m=n\bmod 5$ and let $R$ be a minimal
resolving set of $F_{n}$. For each consecutive, full block of five vertices,
$v_{x},v_{y}\in R$ where $x=5j+2$ so that $v_{x}$ is the second vertex of the
$j^{th}$ block and $y=5j+4$ so that $v_{y}$ is the fourth vertex of the
$j^{th}$ block for $j\geq 0$. If $m\in\\{2,3\\}$, $v_{n}\in R$. If instead
$m=4$, $v_{(n-2)},v_{n}\in R$ (see Figure 4).

Figure 4: A visualization of a minimal resolving set of the fan $F_{n}$ when
$(n\bmod 5)=3$. Dashed lines group separate consecutive blocks of five nodes.

Finally, we claim that $\beta(W_{n})=\beta(F_{n})$ for $n>6$. Indeed, suppose
without loss of generality that $R$ is a minimal resolving set of $F_{n}$ such
that $1,n\not\in R$. (Any resolving set of $F_{n}$ can be made to satisfy this
requirement by replacing $1$ with $2$ or $3$, and $n$ with $n-1$ or $n-2$,
depending on $R\setminus\\{1,n\\}$.) Since the only difference between the fan
and wheel graph is the inclusion of the edge $\\{1,n\\}$ in $W_{n}$, and since
this edge is not required to determine shortest path distances between
elements of $R$ and any other vertices in $W_{n}$, $R$ is also a resolving set
for $W_{n}$. So $\beta(W_{n})\leq\beta(F_{n})$. Conversely, suppose that $R$
is a minimal resolving set of $W_{n}$; in particular, $|R|\leq\beta(F_{n})$.
Then there must be at least one edge $\\{i,j\\}$ in $W_{n}$ such that
$i,j\not\in R$ and $i,j\neq a$. This follows from
$\beta(W_{n})<\lceil\frac{n-1}{2}\rceil$. Removing this edge, therefore, does
not affect $R$ as a resolving set. In particular, $R$ also resolves $F_{n}$
and $\beta(W_{n})=\beta(F_{n})$, which shows (1).

###  5.2 Trees and Unicyclic Graphs

Problems that are computationally difficult on general graph structures often
admit more efficient solutions on trees. This is the case for metric dimension
too. A simple formula giving the metric dimension of trees that are not also
paths [15, 48, 102] leads immediately to a polynomial time algorithm for
finding resolving sets of minimum size on trees. To begin, we present several
important definitions. Let $G=(V,E)$ be a general graph, not necessarily a
tree. In what follows, for $v\in V$, we use $\deg(v)=|\\{u\in V\mid(v,u)\in
E\\}|$ to denote the degree of $v$.

######  Definition 5.1.

(Leaf Vertex.) A vertex $\ell\in V$ is called a leaf when $\deg(\ell)=1$. The
number of leaves in $G$ is denoted $\ell(G)$.

######  Definition 5.2.

(Major Vertex and Terminal Degree.) A vertex $v\in V$ is called a major vertex
when $\deg(v)\geq 3$. The terminal degree of a major vertex $v\in V$ is the
number of leaves $\ell\in V$ such that $d(\ell,v)<d(\ell,u)$, for all other
major vertices $u\in V$.

######  Definition 5.3.

(Exterior Major Vertex.) A major vertex of $G$ is called exterior when its
terminal degree is strictly positive. The number of exterior major vertices in
$G$ is denoted $ex(G)$.

From these definitions, we can write $\beta(G)\geq\ell(G)-ex(G)$, with
equality when $G$ is a tree such that $ex(G)>0$, or equivalently, when $G$ is
not a path [15]. Moreover, any set $R\subset V$ which contains every leaf,
except one, associated with each exterior major vertex is a subset of a
minimal resolving set in $G$. When $G$ is a tree, any such $R$ is resolving
[15]. These observations permit an $O(|V|+|E|)$ algorithm for constructing
minimal resolving sets on trees: after partitioning the leaves of a tree based
on exterior major vertices using a depth first search, one element of each
partition may be dropped to produce a resolving set of minimum size (see
Figure 5).

126127131438459151617101118 Figure 5: A tree of size 18. Vertices 4, 8, 10,
12, 13, 14, 15, 16, 17, and 18 are leaves. The vertices 1, 2, 5, 7, and 9 are
exterior major vertices with terminal degree 2, 1, 2, 2, and 3, respectively.
$R=\\{8,13,15,16,18\\}$ is a resolving set of minimum size.

Let $G=(V,E)$ be a unicyclic graph (i.e. a graph that can be expressed as a
tree with a single additional edge) with $|V|\geq 3$. Let $T$ be any spanning
tree of $G$ and $e$ the only edge in $G$ that is not in $T$. Then
$\beta(T)-2\leq\beta(G)\leq\beta(T)+1$ [15, 90]. As illustrated in Section
2.1, there are unicyclic graphs achieving each of the values in the integer
interval $[\beta(T)-2,\beta(T)+1]$.

To justify the lower bound on $\beta(G)$ for unicyclic $G$, we consider three
cases. First, if $e$ is incident on leaves in $T$ then $\ell(G)=\ell(T)-2$,
and $ex(G)\leq ex(T)$ because $G$ and $T$ have the same major vertices but $e$
reduces the terminal degree of at least one major vertex in $T$. In
particular, $\beta(G)\geq\ell(G)-ex(G)\geq(\ell(T)-2)-ex(T)=\beta(T)-2$.
Instead, if $e$ is incident on exactly one leaf in $T$ then
$\ell(G)=\ell(T)-1$, and $ex(G)\leq ex(T)+1$ because $e$ may turn a vertex in
$T$ into an exterior major vertex. So,
$\beta(G)\geq\ell(G)-ex(G)\geq(\ell(T)-1)-(ex(T)-1)=\beta(T)-2$. Finally, if
$e$ is not incident on any leaf in $T$, $ex(G)\leq ex(T)+2$ because both
vertices $e$ is incident on may become exterior major vertices. Hence,
$\beta(G)\geq\ell(G)-ex(G)\geq\ell(T)-(ex(T)+2)=\beta(T)-2$.

Slightly more work is required to verify the upper bound on the metric
dimension of unicyclic graphs. One approach is to focus on a subset of major
vertices on the cycle in $G$. Let $W$ contain every leaf in $G$, except one,
associated with each exterior major vertex, and let $m$ be the number of major
vertices on the cycle in $G$ with a branch to an element of $W$. Proceeding by
cases, it can be shown that $\beta(G)\leq\beta(T)+1$ whether $m\geq 3$, $m=2$,
$m=1$, or $m=0$ [15].

&

Figure 6: Example of trees $T$ such that, when a single edge (dashed) is added
to form the unicyclic graph $G$, $\beta(G)=\beta(T)-2$ (top left),
$\beta(G)=\beta(T)-1$ (top right), $\beta(G)=\beta(T)$ (bottom left), or
$\beta(G)=\beta(T)+1$ (bottom right) [15]. In each example, red nodes belong
to a resolving set for both $G$ and $T$, light red nodes are used to resolve
$T$, and light blue nodes are used to resolve $G$.

###  5.3 Grids, Honeycombs, and Hexagon Networks

In Section 2.1, we examined two-dimensional grids, $G_{m,n}$, and argued that
$\beta(G_{m,n})=2$. For the $d$-dimensional grid $G_{n_{1},\dots,n_{d}}$
defined in an analogous manner for $n_{i}>1$ for $1\leq i\leq d$,
$\beta(G_{n_{1},\dots,n_{d}})=d$ [66]. The key idea is that if
$r_{0}:=(0,\dots,0)$, and $r_{i}$ is the vector of zeroes with entry
$(n_{i}-1)$ in the $i$-th position, then for any vertex
$v=(x_{1},\dots,x_{d})$ in the grid we have:

$\displaystyle d(r_{0},v)$ $\displaystyle=x_{1}+\dots+x_{d}$ $\displaystyle
d(r_{1},v)$ $\displaystyle=(n_{1}-1-x_{1})+x_{2}+\dots+x_{d}$
$\displaystyle\cdots$ $\displaystyle d(r_{d-1},v)$
$\displaystyle=x_{1}+\dots+(n_{d-1}-1-x_{d-1})+x_{d}.$

Since this linear system of $d$ equations and $d$ unknowns is invertible,
$\\{r_{0},\dots,r_{d-1}\\}$ resolves the grid i.e.
$\beta(G_{n_{1},\dots,n_{d}})\leq d$. The claim follows after showing that the
linear system associated with any set $R$ with fewer than $d$ elements is not
invertible.

Naturally, two-dimensional grids correspond to a square tiling of
$\mathbb{R}^{2}$. Similarly, following the terminology and notation of [77],
the honeycomb networks $HC(n)$ correspond to a partial hexagonal tiling of
$\mathbb{R}^{2}$. More precisely, $HC(1)$ is a single regular hexagon and
$HC(n)$ consists of $n-1$ layers of hexagons around a central one (see Fig. 7,
left). The number of vertices in $HC(n)$ is $6n^{2}$.

The hexagon networks $HX(n)$ correspond also to a recursive and partial tiling
of $\mathbb{R}^{2}$ but with equilateral triangles. $HX(1)$ is, by definition,
a single vertex. $HX(n)$ is a regular hexagon with sides of length $s$ tiled
with equilateral triangles with sides of length $\frac{s}{n-1}$. In
particular, $HX(n)$ has $3n^{2}-3n+1$ vertices from $6(n-1)^{2}$ triangles
(see Figure 8).

Figure 7: Visualization of the honeycomb networks $HC(1)$, $HC(2)$, and
$HC(3)$ from left to right.

Figure 8: Visualization of the hexagon networks $HX(1)$, $HX(2)$, and $HX(3)$
from left to right.

By identifying a useful coordinate system for dealing with distances in
hexagonal graphs, one can show that any three vertices of degree three forming
adjacent corners of the underlying hexagon in $HX(n)$ serve as a resolving set
(see Fig. 9). Since $HX(n)$ violates properties that any graph with metric
dimension two must have [66], we conclude that $\beta(HX(n))=3$ [77].

To determine the metric dimension of $HC(n)$, it is useful to note that
$HC(n)$ is the so-called bounded dual of $HX(n)$. In particular, $HC(n)$ may
be constructed from $HX(n+1)$ as follows. For each face of $HX(n+1)$, except
the unbounded face, include a single vertex in $HC(n)$. Two vertices in
$HC(n)$ are adjacent when the corresponding faces in $HX(n+1)$ share an edge.
By taking advantage of this relationship, it can be shown that
$\beta(HC(n))=3$ as well [77] (see Fig. 9).

$a$$b$$c$$\alpha$$\beta$$\gamma$ Figure 9: Visualization of the honeycomb
network $HC(3)$ (dashed) as the bounded dual of the hexagonal network $HX(4)$
with minimum resolving sets $\\{a,b,c\\}$ and $\\{\alpha,\beta,\gamma\\}$,
respectively, following the construction in [77].

###  5.4 Hamming Graphs

There are many ways to measure distance between pairs of strings. One of the
simplest and most common is the Hamming distance [47]. Comparing two strings
of the same length, the Hamming distance counts the number of positions in
which the strings disagree. This distance can be used to define a graph.

######  Definition 5.4.

(Hamming Graph.) Let $V=A^{k}$ be the set of all strings of length $k$ from
the alphabet $A$ of size $a=|A|$, and let $d(u,v)$ be the Hamming distance
between $u,v\in V$. The Hamming graph $H_{k,a}$ contains a vertex associated
with each $v\in V$ and the edge $\\{u,v\\}\in E$ only when $d(u,v)=1$.

Despite the highly symmetric nature of Hamming graphs, an efficient algorithm
to compute their metric dimension is not known. However, some upper bounds on
$\beta(H_{k,a})$ are known.

For the special case when $a=2$, $Q_{k}:=H_{k,2}$ is called a hypercube. The
hypercube turns out to be an important structure when studying a particular
coin weighing problem: given a set of $k$ coins of two different weights, how
many weighings are required to determine which coins are lighter [103]? An
asymptotic result tells us that
$\lim_{k\rightarrow\infty}\beta(Q_{k})\frac{\log_{2}(k)}{k}=2$, suggesting a
method using $2^{n}-1$ weighings to find the answer when $k=n2^{n-1}$ [32,
75]. This asymptotic behavior generalizes to arbitrary Hamming graphs as
$\lim_{k\rightarrow\infty}\beta(H_{k,a})\frac{\log_{a}(k)}{k}=2$ [61].

Analysis of the Mastermind game, a game closely related to the coin weighing
problem above, depends on the structure of Hamming graphs as well. Mastermind
is played between two players, $A$ and $B$. Player $A$ starts by choosing
$s=s_{1}\dots s_{k}$, a sequence unknown to player $B$ of $k$ symbols from an
alphabet of size $c$. Player $B$ attempts to guess $s$ as quickly possible.
After each guess $q$, player $A$ provides two values: $a(q,s)$, the number of
positions where $q$ and $s$ agree, and $b(q,s)$, the total number of correct
symbols at incorrect positions. Donald Knuth created an algorithm solving the
commercial version of the game with $k=4$ and $c=6$ with at most five
questions [67]. For arbitrary values of $k$ and $c$ a number of results and
bounds exist [20, 40] though there is no known optimal solution.

A static variant of the game in which player $B$ must make all guesses at once
with no feedback and player $A$ only provides $a(q,s)$ has been shown to be
NP-complete [42]. Indeed, notice that $a(q,s)=k-d(q,s)$, where $d(q,s)$ is the
Hamming distance between the two sequences. In particular, to guess $s$ with
the least number of questions, player $B$ should make guesses that reveal the
Hamming distance from $s$ to a resolving set of $H_{k,c}$ of size
$\beta(H_{k,c})$. A deeper analysis of this situation yields an upper bound on
$\beta(H_{k,c})$ when $k$ is small in comparison to $c$. In particular, if
$\epsilon<1$ and $c<k^{1-\epsilon}$ then
$\beta(H_{k,c})\leq(2+\epsilon)k\frac{1+2\log_{2}(c)}{\log_{2}(k)-\log_{2}(c)}$
[20].

Bounds related to the metric dimension of Cartesian product of graphs have
proven useful in studying Hamming graphs. In particular,
$\beta(G)\leq\beta(G\square K_{2})\leq\beta(G)+1$ [15] and, since
$H_{k,a}=K_{a}^{\square k}$ is the Cartesian product of $k$ copies of the
complete graph $K_{a}$, it follows that
$\beta(Q_{k})\leq\beta(Q_{k+1})\leq\beta(Q_{k})+1$. This approach yields the
identity $\beta(H_{2,a})=\lfloor\frac{2}{3}(2a-1)\rfloor$ [12]. Table 1 shows
exact values of $\beta(Q_{k})$ verified via brute force for $1\leq k\leq 10$,
and upper bounds based on a variable neighborhood search for $11\leq k\leq 17$
[85].

$k$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$\beta(Q_{k})$ | 1 | 2 | 3 | 4 | 4 | 5 | 6 | 6 | 7 | 7 | 8 | 8 | 8 | 9 | 9 | 10 | 10
Table 1: Exact values of $\beta(Q_{k})$ for $1\leq k\leq 10$, and upper bounds
for $11\leq k\leq 17$ [85].

The bounds for the metric dimension of hypercubes have been generalized for
arbitrary Hamming graphs as
$\beta(H_{k,a})\leq\beta(H_{k+1,a})\leq\beta(H_{k,a})+\lfloor\frac{a}{2}\rfloor$
[108]. The proof is constructive allowing for the generation of $R_{k+1}$, a
resolving set for $H_{k+1,a}$, from $R_{k}$, any resolving set for $H_{k,a}$.

When dealing with very large Hamming graphs, verifying that a given subset of
vertices is resolving becomes intractable via the simple brute force approach.
However, the recursive structure and highly symmetric nature of Hamming graphs
allows for far more efficient resolvability checks in practice. Indeed, by
describing resolvability on Hamming graphs as a linear system, integer
programming techniques can be used to verify quickly that a given set of
vertices is resolving with high probability. A somewhat slower but
deterministic solution can be implemented using Gröbner bases. These
techniques have been used to discover a resolving set of size 77 for the
Hamming graph $H_{8,20}$, showing that $\beta(H_{8,20})\leq 77$ [72]. With
25.6 billion vertices, traditional methods for finding small resolving sets
are not computationally feasible in this setting.

Graph Type | Symbol (constraint) | Metric Dimension | Reference
---|---|---|---
Antiprisms |  $A_{n}\,(n\geq 3$) | 3 | [60]
Complete Graphs | $K_{n}$ | $n-1$ | [15]
Cycles | $C_{n}$ | 2 | [16]
De Bruijn Graphs | $B_{d,n}$ | $d^{n-1}(d-1)$ | [35, 92]
Fans | $F_{n}\,(n\not\in\\{1,2,3,6\\})$ | $\lfloor\frac{2n+2}{5}\rfloor$ | [51]
Grids in $d$ dimensions | $G_{m,n,\dots}$ | $d$ | [66, 82]
Hexagonal Graphs | $HX(n)$ | 3 | [77]
Honeycomb Graphs | $HC(n)$ | 3 | [77]
Jahangir Graphs | $J_{2n}\,(n\geq 4)$ | $\lfloor\frac{2n}{3}\rfloor$ | [110]
Kautz Graphs | $K_{d,n}$ | $(d^{n-1}+d^{n-2})(d-1)$ | [35, 92]
Paths | $P_{n}$ | 1 | [15]
Peterson Graphs | $P_{n,2}\,(n\geq 5)$ | 3 | [60]
Prisms | $D_{n}$ |  2 for odd $n$, 3 for even $n$ | [60]
Trees | $T_{n}$ | $\ell(T_{n})-\text{ex}(T_{n})$ | [15, 48, 102]
Wheels | $W_{n}\,(n>6)$ | $\beta(W_{n})=\beta(F_{n})$ |  § 5.1, [99]
Table 2: Exact values for the metric dimension of several different families of graphs. Graph Type | Symbol (constraint) | Metric Dimension | Reference
---|---|---|---
Bilinear Forms Graphs | $H_{q}(n,d)\,(n\geq d\geq 2)$ | $\beta(H_{q}(n,d))\leq q^{n+d-1+\lfloor\frac{d+1}{n}\rfloor}$ | [34]
Cartesian Product with $K_{2}$ | $G\times K_{2}$ | $\beta(G)\leq\beta(G\times K_{2})\leq\beta(G)+1$ | [15]
Doubled Odd Graphs | $O(2e+1,e,e+1)\,(e\geq 2)$ | $\beta(O(2e+1,e,e+1))\leq 2e+1$ | [45]
Hamming Graphs | $H_{k,a}$ | $\beta(H_{k,a})\leq\beta(H_{k+1,a})\leq\beta(H_{k,a})\\!+\\!\lfloor a/2\rfloor$ | [108]
Johnson Graphs | $J(n,e)$ | $\beta(J(n,e))\leq(e+1)\lceil n/(e+1)\rceil$ | [5, 45]
Unicyclic Graphs | $T+e$ | $\beta(T)-2\leq\beta(T+e)\leq\beta(T)+1$ | [15]
Table 3: Bounds on the metric dimension of several different families of graphs. Graph Type | Metric Dimension
---|---
Benes Networks |  Polynomial time solvable, see reference [79]
Butterfly Networks |  Polynomial time solvable, see reference [79]
Cactus Block Graphs |  Linear time solvable, see reference [53]
Chain Graphs |  Linear time solvable, see reference [36]
Cographs |  Linear time solvable, see reference [30]
Outerplanar Graphs |  Polynomial time solvable, see reference [27]
Table 4: Families of graphs for which metric dimension can be determined efficiently. Graph Type | Metric Dimension
---|---
Amalgamation of Cycles |  See page 25 of reference [57]
Cayley Digraphs |  See pages 34-37 of reference [33]
Circulent Networks |  See reference [93]
Complete $k$-partite Graphs |  See reference [95]
Generalized Wheel Graphs |  See reference [104]
Graphs with Pendant Edges |  See pages 4-7 of reference [58]
Grassmann Graphs |  See page 98 of reference [81]
Harary Graphs $H_{4,n}$ |  See page 9 of reference [60]
Kneser Graphs |  See page 750 of reference [5]
Line Graphs |  See pages 803-804 of reference [35]
Regular Bipartite Graphs |  See pages 16-17 of reference [4]
Torus Network |  See pages 268 and 271 of reference [78]
Twisted Grassmann Graphs |  See page 4 of reference [45]
Table 5: Additional families of graphs for which metric dimension can be
determined efficiently. See [51] for additional bounds.

##  6 Random Graph Models

Real world networks rarely fully conform to the requirements for structurally
deterministic graph families. Random graph models, which define distributions
over graph structures, often in terms of some generative process, are
therefore useful in describing real networks. Understanding the behavior of
metric dimension as a random variable with respect to these distributions
allows for the general study of metric dimension, resolving sets, and
efficient means for finding small resolving sets in some situations. Though
there has not been as much work on metric dimension in this context as
compared to deterministic graphs, there have been several significant
contributions in this area concerning Erdös-Rényi random graphs [9], and
random trees and forests [84].

###  6.1 Erdös-Rényi Random Graphs

For each $0\leq p\leq 1$, let $G_{n,p}$ denote a (simple) random graph with
$n$ vertices obtained by including each of the possible ${n\choose 2}$ edges
with probability $p$, independently of all other edges.

As $n\rightarrow\infty$, the set of $\lceil(3\log n)/\log 2\rceil$ highest
degree vertices in $G_{n,1/2}$ suffices as a resolving set with high
probability [3]. This upper bound on $\beta(G_{n,1/2})$ was originally used as
part of a simple heuristic algorithm for canonically labeling graphs and
determining whether or not two graphs are isomorphic [3]. More recently,
focusing solely on adjacency information in $G_{n,p}$, this bound has been
generalized for arbitrary values of $p$ to
$\beta(G_{n,p})\leq\frac{-3\ln(n)}{\ln(p^{2}+(1-p)^{2})}$ [109, 106]. The
proof of this generalization does not rely on choosing a resolving set based
on any particular property. In fact, any subset of nodes in $G_{n,p}$ of size
at least $\frac{-3\ln(n)}{\ln(p^{2}+(1-p)^{2})}$ is a resolving set with high
probability for large $n$.

Detailed insight into the metric dimension of Erdös-Rényi graphs can be gained
from the following result where $p$ is a function of $n$.

######  Theorem 6.1 (Adapted from [9]).

Let $d=(n-1)p$ be the expected degree. Suppose that log^5 n ≪d ≤n (
1-3log(logn)logn ). Let $i\geq 0$ be the largest integer such that
$d^{i}=o(n)$ and let $c=c(n)=e^{d^{i+1}/n}$. If $\beta_{n}$ denotes the metric
dimension of $G_{n,p}$, then the following holds asymptotically almost surely.

$\beta_{n}=\begin{cases}\Theta(\log n)&\hbox{ if }c=\Theta(1),\\\ \Theta(c\log
n)&\hbox{ if }c^{-1}=\Omega(d^{i}/n),\\\ \Theta(\frac{n\log n}{d^{i}})&\hbox{
if }c^{-1}\ll d^{i}/n.\end{cases}$

The regimes of $p$ described in this theorem produce a zig-zag pattern in
$\beta(G_{n,p})$ as a function of $p$. Indeed, it can be shown that
$\log_{n}(\beta(G_{n,n^{x-1}}))$, for $0<x<1$, approaches the function
$f(x)=1-x\lfloor 1/x\rfloor$ as $n\to\infty$ with high probability [9].

In a dense graph (i.e. with many edges and low path length entropy), consider
picking a single vertex $v$ to add to a growing resolving set. This vertex
defines an equivalence relation on the graph: two vertices are equivalent if
they are the same distance away from $v$. In terms of distances and
cardinalities, the equivalence classes are nearly the same—regardless of the
vertex chosen. The ratio between the sizes of the two largest equivalence
classes has great influence on the overall metric dimension. When this ratio
is close to 1, picking a new vertex to add to the growing resolving set from
the largest class will, on average, lead to more new equivalence classes than
when the largest equivalence class contains many more vertices than the second
largest. So, the overall metric dimension might be smaller the closer the two
largest equivalence classes are in terms of size [9].

The zig–zag pattern observed in $\beta(G_{n,p})$ comes from how this ratio
evolves in $G_{n,p}$ with decreasing $p$. Let $D_{v}(i)$ denote the set of
vertices at a distance $i$ from a chosen vertex $v$. When $p=1$, the graph is
complete and $|D_{v}(0)|=1$ and $|D_{v}(1)|=n-1$ for all vertices $v$ so that
$\beta(G_{n,1})=n-1$. As $p$ decreases, $|D_{v}(i)|$ for $i>1$ increases. At
first, this increase is faster for smaller values of $i$. Eventually,
$|D_{v}(1)|\approx|D_{v}(2)|$ and the metric dimension is small. Decreasing
$p$ further, the sizes of the two largest distance sets move away from one
another and the ratio between their sizes increases. This pattern then repeats
itself as the identities of the largest sets change [9].

Given two random variables, $X$ and $Y$, define the following measure of
similarity between their distributions:

$d(X,Y):=\sup_{h}\frac{E(h(X))-E(h(Y))}{\sup_{x}|h(x)|+\sup_{x}|h^{\prime}(x)|}$

where the supremum is taken over all bounded test functions
$h:\mathbb{R}\to\mathbb{R}$ with bounded derivative, and $E(\cdot)$ is used to
denote expectation. The behavior of $\beta(G_{n,p})$ when $p$ is comparatively
small is described by the following result. (The previous result addressed the
case when $p$ is not as small.)

######  Theorem 6.2 ([84]).

Let $\beta_{n}$ denote the metric dimension of $G_{n,p}$.

  * (i)

For $p=o(n^{-1})$, $\beta_{n}=n(1+o(1))$ asymptotically almost surely.

  * (ii)

For $p=c/n$ with $0<c<1$, the sequence of random variables X_n = βn\-
E(βn)Var(βn) converges in distribution to a standard normal random variable
$Z$ as $n\rightarrow\infty$, at a rate $d(X_{n},Z)=O(n^{-1/2})$. Moreover,
$E(\beta_{n})=Cn(1+o(1))$ and $Var(\beta_{n})=\Theta(n)$, where $C$ is an
explicit constant that depends on $c$ only.

###  6.2 Stochastic Block Model

The Stochastic Block Model (SBM) is a generative graph model used frequently
to study networks with simple community structure. In its most basic form, the
SBM has two main parameters, $C$ and $P$. $C$ is a partition of $n$ vertices
into $c\geq 1$ disjoint communities $C_{1},\dots,C_{c}$, and $P$ is a
$(c\times c)$ symmetric matrix of adjacency probabilities. The communities are
also sometimes defined stochastically using a probability vector of dimension
$c$.

We say $G\sim SBM(n;C,P)$ when, for $u\in C_{i}$ and $v\in C_{j}$ with $u\neq
v$, $\\{u,v\\}\in E$ with probability $P_{i,j}$, the entry in row-$i$ and
column-$j$ of $P$, independently of all other pairs of nodes. Considered
separately, each individual community is equivalent to an Erdös-Rényi random
graph. This immediately suggests that approaches used to determine bounds on
$\beta(G_{n,p})$ may prove valuable in this context as well. Inter-community
adjacency probabilities, however, complicate the situation and must be dealt
with carefully. For example, given $c=2$ and

$P=\begin{bmatrix}o(1)&\frac{1}{2}\\\ \frac{1}{2}&o(1)\end{bmatrix}$

the communities of the resulting graph will be sparse and individual vertices
may be difficult to distinguish without the help of vertices from both
communities. Unfortunately, characterizing the precise interaction between
vertices from different communities is not trivial, especially given the
complicated dependencies between shortest path distances in such graphs.

It can be shown that the adjacency metric dimension of a graph, i.e. the
metric dimension when only only neighbors of a node can be used to distinguish
it from other nodes, serves as an upper bound on metric dimension [59]. In
particular, since the entries in the adjacency adjacency matrix of the SBM are
by definition independent, a probabilistic upper bound on the metric dimension
of these kinds of graphs can be established [109, 106]. Indeed, letting
$\mathbb{P}(G;R)$ denote the probability that there are nodes in $G\sim
SBM(n;C,P)$ with the same neighbors in $R$ where $R\subseteq\\{1,\ldots,n\\}$
contains $k_{i}$ nodes in community $i$, the first-moment method implies that

$\mathbb{P}(G;R)\leq\sum_{1\leq i\leq j\leq
c}|V_{i}||V_{j}|\prod_{\ell=1}^{c}P_{i,\ell}P_{j,\ell}+(1-P_{i,\ell})(1-P_{j,\ell})^{k_{\ell}}.$

This inequality serves as the basis of an effective, fast algorithm, for
selecting vertices in $G$ such that $\sum_{1\leq i\leq c}k_{i}$ is minimized
and $\mathbb{P}(G;R)$ is less than a given threshold value. In essence, this
algorithm provides an intelligent strategy for determining how the vertices of
small resolving sets should be distributed across communities for any graph
$G\sim SBM(n;C,P)$ with fixed parameters [109, 106].

###  6.3 Random Trees and Forests

The metric dimension of a disconnected graph is, by definition, the sum of
metric dimension of the graphs induced by its connected components. This is
because the distance between any two vertices from different components is
regarded as $\infty$. Accordingly, it is not surprising that the metric
dimension of $F_{n}$, a forest on $n$ vertices chosen uniformly at random, has
the same limiting distribution as that of $T_{n}$ [84], a tree on $n$ vertices
also chosen uniformly at random. Furthermore, if $\beta_{n}=\beta(T_{n})$
then, as $n\rightarrow\infty$, the random variables

$X_{n}=\frac{\beta_{n}-E(\beta_{n})}{\sqrt{Var(\beta_{n})}}$

converge in distribution to a standard normal, where $E(\beta_{n})=\mu
n(1+o(1))$ and $Var(\beta_{n})=\sigma^{2}n(1+o(1))$, with $\mu\simeq
0.14076941$ and $\sigma^{2}\simeq 0.063748151$ (see Fig. 10).

Figure 10: Histogram of the metric dimensions of 1000 random trees on 2000
vertices (blue bars), along with the probability density function of a
standard normal distribution (red curve). The Jarque-Bera test produces a
$p$-value of $0.222$; in particular, the data carries little to no evidence
against the null hypothesis that it comes from a standard Gaussian.

##  7 Applications

Small resolving sets are useful in a variety of situations. The direct analogy
between metric dimension and trilateration in the plane makes potential
applications regarding navigation [66] and location detection [102] in
discrete space immediately apparent. Resolving sets have also been used as a
means of comparing graphs. The classification of chemical compounds based on
general chemical structure can be accomplished using resolving sets [15, 62,
63]. One method for quickly determining whether many, though not all, pairs of
graphs are isomorphic relies on comparing vertex representations based on
presumed resolving sets [3]. In this section, we examine several applications
of resolving sets including as observers in detecting the source of a spread
over a network [105], as a tool for detecting network motifs [56], and as the
basis of a method for embedding DNA sequences in real space [108].

###  7.1 Source Localization

A variety of transmission processes, such as information and disease, occur on
networks. News and rumors circulate over social networks like Facebook and
Twitter, and businesses take advantage of “influencers” to maximize the effect
of marketing campaigns [10, 65, 71, 111]. Physical interaction networks are
often used as a tool for studying the spread of diseases across communities
[86, 87, 88, 89]. In many contexts, it is valuable to locate the source of a
transmission process, the node or set of nodes from which the spread began,
for example to better understand the process and to decrease/increase
transmission speed. Existing approaches to solving this problem include
dynamic message passing [76], time-reversal [100], and maximum likelihood
estimators [89, 98].

Small resolving sets can also provide an elegant solution to source
localization. As a concrete example, suppose that a transmission process on
the graph $G=(V,E)$ starts at an unknown source $s\in V$ at time $t_{0}$ and
travels at unit speed across the edges. Suppose we can pre-specify a set
$R\subseteq V$ of observation nodes, such that we will observe the times
$t_{r}$ at which the process first reaches each node $r\in R$. A natural
question is therefore, for which sets $R$ can we infer the source location $s$
from the observation times $\\{t_{r}\\}_{r\in R}$ [89, 117]? The answer:
exactly the sets $R$ which are resolving for $G$. By definition of the
process, we will have $t_{r}-t_{0}=d(r,s)$, and thus the observation times
uniquely identify $s$, for all possible sources $s$, exactly when $R$ is a
resolving set.

While resolving sets present a promising solution to source localization,
there are two non-trivial difficulties that arise in real-world transmission
processes which require attention. First, it is very unlikely that the start
time $t_{0}$ of the process will be known. Second, the speed $\ell_{e}$ at
which information or diseases traverse a given edge $e\in E$, often called the
edge length, is rarely deterministic or known precisely. Instead, edge lengths
are often modeled as randomly drawn from some known distribution.

An unknown start time may be addressed by strengthening the notion of
resolving sets to that of doubly resolving sets [12, 105]; see also Section
8.1. We call $R\subseteq V$ _doubly resolving_ when for every pair of nodes
$u,v\in V$ there is a pair $r,r^{\prime}\in R$ such that
$d(r,u)-d(r^{\prime},u)\neq d(r,v)-d(r^{\prime},v)$. If $R$ is doubly
resolving, it is also resolving. Furthermore, one easily calculates
$d(r,v)-d(r^{\prime},v)=t_{r}-t_{0}-t_{r^{\prime}}+t_{0}=t_{r}-t_{r^{\prime}}$
for all nodes $v\in V$ and $r,r^{\prime}\in R$. Thus, as doubly resolving sets
are based on relative and not absolute distances, the source can once again be
located from the set $\\{t_{r}\\}_{r\in R}$ even if the start time $t_{0}$ is
unknown.

Random edge lengths are more difficult to address and solutions depend on the
details of the transmission process. When the variance of $\ell_{e}$ is low
relative to its mean, observation times will be close to their expected value,
and resolving sets allow for exact solutions with high probability. When the
variance of $\ell_{e}$ is high, however, observation times will carry very
little information about the expected distances, especially for nodes $v$ at
greater distance from the source $s$. In this case, we can increase accuracy
by adding nodes to $R$ using a path covering strategy such as truncated metric
dimension (Section 8.4). In this way, distances between observation nodes are
small and thus noise accumulation is low, and we maintain resolvability of
expected distances [105].

###  7.2 Detecting Network Motifs

A common tool in network science to compare graphs is via motifs, which are
subgraphs appearing with higher than expected frequency. Network motifs are
believed to play important roles in the structure and underlying dynamics of
networks in a variety of fields including social sciences [55, 54], biology
[28, 43, 73, 101], chemistry [46, 116], and data mining more generally [21,
112, 114]. By finding and analyzing these motifs, researchers gain insight
into the functional properties of different systems. The problem of
discovering important subgraphs in a large network, however, poses significant
computational challenges: the subgraph isomorphism problem, determining
whether or not a given graph occurs as a subgraph in a larger graph, is NP-
complete [22, 115]. On the other hand, graph isomorphism, the special case of
subgraph isomorphism when the graphs have the same size, is believed to be an
easier problem [96, 25], especially given the recent quasi-polynomial time
algorithm [2]. A natural algorithm to count $k$-node motifs is therefore to
enumerate subgraphs of size $k$ and test whether they are isomorphic to the
given motif. Resolving sets and metric dimension have been used as the
foundation of tools to solve graph isomorphism [3], and in the manner above,
for motif detection [56].

One technique to solve graph isomorphism is through a _canonical labeling_ , a
way to assign unique labels to nodes which is invariant under graph
isomorphism. Since resolving sets provide a unique label for each node in a
graph, they can serve as the basis of such labelings. In particular, suppose
that one could uniquely identify a resolving set $R$ given a graph $G=(V,E)$,
and furthermore, uniquely identify an ordering $R=\\{r_{1},\ldots,r_{|R|}\\}$.
Then assigning label $d(u|R)\in\mathbb{R}^{|R|}$ to each node $u\in V$ will
give a canonical labeling, as both $R$ and the ordering is uniquely determined
by $G$, and given $R$ and this ordering, the distance vectors are unique as
$R$ is resolving.

Using this general approach, the following quadratic-time canonical labeling
algorithm provably solves graph isomorphism with high probability for Erdös-
Rényi random graphs $G_{n,p}$, that is, graphs on $n$ vertices such that each
edge appears with independent probability $p$ [3]. Consider a graph $G=(V,E)$
and let $n=|V|$ and $R=\\{r_{1},\dots,r_{|R|}\\}$ be the set of the
$\lceil(3\log(n))/\log(2)\rceil$ highest degree vertices in $V$.222In fact,
any set of vertices of this size will suffice as a resolving set with high
probability, not just vertices of high degree. This fact is directly related
to the fact that the degree distribution of $G_{n,p}$ is Binomial, and
therefore concentrated around its mean [1, 24]. The algorithm labels each
vertex in $G$ with the set of nodes in $R$ which are adjacent. (This step of
the algorithm leverages the fact that the diameter of $G_{n,p}$ is 2 with high
probability as $n$ increases, so the set of adjacent $R$ nodes is equivalent
to the distance vector $d(\cdot|R)$.) This labeling is canonical, i.e.,
invariant under isomorphism, as long as no pair of vertices in $R$ have the
same degree, and the labels are unique. Under $G_{n,1/2}$, Erdös-Rényi random
graphs with adjacency probability $\frac{1}{2}$, the probability that this
algorithm succeeds in finding a canonical labeling is at least
$1-\sqrt[7]{1/n}$ for large $n$ [3]. This technique indirectly shows that
$\beta(G_{n,1/2})\leq\lceil(3\log(n))/\log(2)\rceil$; more generally, it can
be shown that $\beta(G_{n,p})\leq\frac{-3\ln(n)}{\ln(p^{2}+(1-p)^{2})}$ [109,
106].

Another recent algorithm uses the above technique more explicitly, by directly
computing a canonical resolving set and ordering [56]. The approach is as
follows. Enumerate all resolving sets $R$ of size $\beta(G)$ and permutations
$\pi$, and compute the corresponding adjacency matrix $A_{R,\pi}$ for each. In
$A_{R,\pi}$, the vertices of $G$ are ordered lexicographically with respect to
their distance vectors $d(\cdot|R)$ ordered by $\pi$. Now take $R$ and $\pi$
such that $A_{R,\pi}$ is lexicographically first (after flattening) among all
such choices. Given this choice of $R$ and $\pi$, labeling the vertices of $G$
by their distance vector representations gives a canonical labeling.

This approach can be time consuming, as it requires computing (an upper bound
for) $\beta(G)$ and enumerating all resolving sets $R$ of this size and all
orderings on these sets. One can improve performance slightly by ignoring the
relative ordering of twin vertices (§ 4.2) [56]. Tests on a wide variety of
graphs show that this method is effective but somewhat slower than the graph
isomorphism tool provided with nauty [80]. However, this method is faster than
nauty on multi-dimensional mesh graphs, and was the core algorithm in a tool
for identifying and counting statistically significant subgraphs in the
transcriptional regulation networks of _Saccharomyces cerevisiae_ (yeast) and
_Escherichia coli_ (_E. coli_) [56].

###  7.3 Embedding Biological Sequence Data

High-throughput sequencing technologies have enabled biologists to collect a
wealth of DNA, RNA, and amino acid sequence data. The abundance of this
information makes computational analysis methods, including those based on
machine learning algorithms, indispensable. The majority of these methods,
however, cannot directly learn from symbolic data, like biological sequences,
and deal instead with numeric vectors. Methods to embed symbolic sequences
into real vector spaces are thus an important pre-processing step [108]. Low-
dimensional embeddings are especially useful, both to reduce the computational
cost of learning algorithms and to avoid overfitting.

Consider the task of embedding a sequence of length $\ell$, composed of
symbols from an alphabet of size $a$, into a real vector space. For example,
DNA and RNA sequences have $a=4$, while amino acids are composed of $a=20$
possible symbols. A naïve approach to this embedding is the so-called “one-hot
encoding”, which simply generates an indicator vector for each of the
$a^{\ell}$ possible sequences of length $\ell$. This approach is untenable for
most biological sequence data, where $\ell$ can be quite large. One lower-
dimensional approach to embed such sequences uses binary representations,
which indicate the presence or absence of each character in the alphabet at
each position in the sequence, thus requiring $a\cdot\ell$ dimensions [13].
Another common approach uses $k$-mer count vectors, which count the number of
times that every possible contiguous subsequence of length $k$ occurs in the
larger sequence using a sliding window [74]. Unlike one-hot encodings and
binary representations, $k$-mer count vectors are not guaranteed to produce an
injective embedding. These $k$-mer count vectors are $a^{k}$-dimensional;
typically one chooses $k\ll\ell$.

Resolving sets can be applied to this problem a well. Often the domain of
interest has some natural distance metric between sequences. For biological
sequences and several other domains, a natural choice is Hamming distance,
which simply counts the number of indices in which the two sequences differ.
The Hamming distance induces the Hamming graph $H_{\ell,a}$ on length-$\ell$
sequences from $a$ symbols, where there are edges between sequences which
differ in only one entry, and hence the path length between two sequences is
their Hamming distance (Section 5.4). Given a resolving set $R$ on
$H_{\ell,a}$, each sequence can be uniquely represented by its vector of
distances to the elements of $R$. These distance vectors are therefore an
injective $|R|$-dimensional embedding, and the metric dimension of
$H_{\ell,a}$ gives the smallest possible embedding dimension for this
approach.

Embeddings based on resolving sets of $H_{3,4}$ were used as features to
classify DNA sequences of length 20 as being centered at intron-exon
boundaries, or not, in the fruit fly genome [108]. In this study, the
resolving set embedding outperforms $k$-mer count vector and binary
representation based features with respect to accuracy and specificity, and is
competitive with features based on other state-of-the-art embedding techniques
like Node2Vec [44] and multidimensional scaling [70].333For this particular
task, $k$-mer count vectors are not well suited. As positive examples consist
of half intronic and half exonic DNA, we might expect the location of $k$-mers
within the larger sequence to matter a great deal, yet $k$-mer count vectors
do not directly encode this information. Resolving set embeddings are also
generally more compact than those based on $k$-mer count vectors or binary
representations. For example, part of the genome of the Dengue virus codes for
a protease that targets octapeptides, amino acid sequences of length 8, in
human cells. While the space of all octapeptides is large, consisting of
$25.6$ billion sequences, no more than $82$ are required for a resolving set.
Based on such a set, $H_{8,20}$ may be embedded in $\mathbb{R}^{82}$. In
comparison, $3$-mer count vectors use $8,000$ dimensions while a binary vector
representation requires 160 dimensions [108].

##  8 Related Concepts

There are a wide variety of concepts closely linked to metric dimension. Some
strengthen or alter the constraints placed on the identifiability of nodes
while others are extensions of the concept itself. In this section we will
briefly define several such notions. A survey by Chartrand and Zhang [19]
contains more complete characterizations of several of these concepts as well
as information on concepts not mentioned here. There is also a body of work on
conditional resolvability which focuses on resolving sets that have some
additional property. For example, one can consider the smallest resolving set
of a graph that induces a connected subgraph, or that is also an independent
set. For these conditional variants, we direct the reader to a survey by
Saenpholphat and Zhang [94].

###  8.1 Doubly Resolving Sets

As discussed in Section 7.1, while one can uniquely identify all nodes in a
graph based on distances to a resolving set, this identification can fail if
one only knows distances up to an additive constant. Doubly resolving sets
address this shortcoming and have proven useful in identifying the source of a
spread in a network [105] and in determining bounds on the metric dimension of
Cartesian products of graphs [12]. In particular, a set $R\subseteq V$ is
called _doubly resolving_ if, for every pair of nodes $u,v\in V$, there is a
pair $r,r^{\prime}\in R$ such that $d(r,u)-d(r^{\prime},u)\neq
d(r,v)-d(r^{\prime},v)$. Such sets differentiate nodes based on relative as
opposed to absolute distances.

For example, consider the path graph $P_{n}$ with nodes labeled consecutively
from $1$ to $n$ and resolving set $\\{1\\}$. Suppose a signal is sent along
the path from some node $i$ at arbitrary time $t$. Traversing each edge in one
time unit, this signal reaches node $1$ at time $(t+i-1)$. Since $t$ is
unknown, node $i$ cannot be distinguished as the source of the signal from
this information alone. The set $\\{1,n\\}$, on the other hand, is doubly
resolving on $P_{n}$. Now a signal sent from $i$ at time $t$ will arrive at
node $1$ at time $(t+i-1)$ and at node $n$ at time $(t+n-i)$. So, for any node
$j\neq i$, $d(i,1)-d(i,n)=(t+i-1)-(t+n-i)=2i-n-1\neq
2j-n-1=(t+j-1)-(t+n-j)=d(j,1)-d(j,n)$ and the source of the signal can be
uniquely determined.

###  8.2 Strong Metric Dimension

Since all vertices in a graph $G=(V,E)$ are distinguished based on distances
to a resolving set $R\subseteq V$, it is tempting to think that $G$ may be
reconstructed using $R$. These distances can only recover shortest paths,
however, and thus any edge in $E$ that is not part of a unique shortest path
from any $v\in V$ to any $r\in R$ could be excluded in such a reconstruction.
For example, consider the cycle $C_{6}$ with the minimum resolving set
$R=\\{1,3\\}$. Notice $R$ remains a minimum resolving set if the edge $(2,5)$
is added. Furthermore, for each $v\in V$, $d(v|R)$ is the same with or without
this extra edge. As a result, $R$ is not enough to guarantee a faithful
reconstruction of $C_{6}$. Notably, any resolving set is enough to reconstruct
a tree, as the only path between any pair of vertices is the shortest path.

A set $S\subseteq V$ is said to _strongly resolve_ $G$ if for every $u,v\in V$
there is a vertex $s\in S$ such that $u$ lies on a shortest path from $s$ to
$v$ or $v$ lies on a shortest path from $s$ to $u$ [97]. The size of smallest
possible strongly resolving sets on a graph is its strong metric dimension. By
definition, every edge in $E$ must be accounted for by a shortest path
distance $d(v,s)$ for some $v\in V$ and $s\in S$. This allows $G$ to be
reconstructed exactly based on a strong resolving set [97]. For a survey of
results and approximation methods related to strong metric dimension see [68].

###  8.3 Multilateration

The definition of metric dimension depends heavily on graph structure and a
notion of edge distances. Yet there are pairwise distance matrices that do not
correspond to a graph or metric space. Consider the following matrix:

$M=\blockarray$ &ABC c(ccc)A010100 B∞010 C∞∞0

Notice that the points in $M$ do not abide by the triangle inequality. While
we can circumvent the fact that values in this matrix are not symmetric by
using directed edges, violating the triangle inequality would require
redefining the distance between pairs of nodes. Fortunately, metric dimension
makes no use of the actual distance between two vertices beyond checking
equality, and thus one can imagine a relaxation using a more general distance
function. In fact, one could even allow the entries of $M$ to come from an
arbitrary set other than the reals.

This more general problem on arbitrary matrices is called _multilateration_
[108]. Let $I$ be a set of items associated with the rows of a matrix $M$ and
$F$ be a set of functions over $I$ associated with columns such that
$M(i,f)=f(i)$. Analogous to metric dimension, the goal of multilateration is
to determine a resolving set $R\subseteq F$ of minimum size such that the
vectors $(r(i))_{r\in R}$ are unique for all $i\in I$. One can equivalently
think of $R$ as a set of columns of $M$ such that the row vectors of the
induced submatrix are unique. Borrowing notation from metric dimension, we set
$\beta(M)=|R|$ for a set $R$ of minimum size. The entries $M(i,f)$ need not be
numeric; one only needs a notion of equivalence on elements of $f(I)$ for each
$f\in F$, i.e., for values in the same column of $M$. In the context of
graphs, multilateration is equivalent to metric dimension: if $G$ is a graph
with pairwise distance matrix $D$, then we have $\beta(G)=\beta(D)$.

###  8.4 Truncated Metric Dimension

In some scenarios, complete distance information of a network is unavailable.
In particular, perhaps only distances below a certain threshold are available,
perhaps because collecting long-distance information is costly or prone to an
excessive amount of noise. In such cases it may not be possible to determine
the metric dimension of the full graph. Instead, given a graph $G=(V,E)$ and a
maximum distinguishable distance $k$, let $d_{k}(u,v)=\min\\{d(u,v),k+1\\}$ be
the $k$-truncated distance between $u,v\in V$ and let $D_{k}$ be the
$k$-truncated distance matrix of $G$. Then the $k$-truncated metric dimension
of $G$ is defined as $\beta_{k}(G)=\beta(D_{k})$, where $\beta(D_{k})$ is
defined as in multilateration (Section 8.3) [107, 106]. This notion is a
generalization of the concept of adjacency metric dimension [59] where $k=1$
and vertices are distinguished by their neighbors in a resolving set.

Beyond settings with restricted distance information, truncated metric
dimension can also be an effective tool for studying metric dimension. For
instance, it can be shown that for all graphs $G$ and all $k\geq 1$, we have
$\beta(D_{k})\geq\beta(D_{k+1})$ [107, 106]; as $\beta(G)=\beta(D_{n-1})$,
this means truncated metric dimension can give upper bounds on $\beta(G)$. As
one application, an asymptotically tight upper bound on the metric dimension
of the Erdös-Rényi random graph $G_{n,p}$ can be determined by focusing on
$\beta(D_{1})$, i.e., on adjacency information alone [109, 106]. While
$G_{n,p}$ contains dependencies between shortest path lengths, adjacencies are
independent by definition, making the $1$-truncated metric dimension of these
graphs far easier to characterize than their standard metric dimension
(Section 7.2).

###  8.5 Resolving Number, Upper Dimension, Random $k$-dimensionality

Given a resolving set $R$ of $G=(V,E)$, it is natural to consider removing
elements of $R$ while keeping the set resolving. Let $\mathcal{R}(G)$ be the
set of all resolving sets which cannot be made smaller in this way, i.e., for
which no proper subset $S\subset R$ is also resolving. Resolving sets
$R\in\mathcal{R}(G)$, while minimal in the sense of set inclusion, are not
guaranteed to be minimal in the sense that $|R|=\beta(G)$, the minimum
possible size of any resolving set of $G$. For example, on the path $P_{6}$ on
vertices $\\{1,\ldots,6\\}$, the set $R=\\{3,4\\}$ is in $\mathcal{R}(P_{6})$,
but $\beta(P_{6})=1$, achieved by $\\{1\\}$. As resolving sets of cardinality
$\beta(G)$ are also elements of $\mathcal{R}(G)$, however, we do have
$\beta(G)=\min_{R\in\mathcal{R}(G)}|R|$. The size of largest set-inclusion-
minimal resolving set, on the other hand, is called the _upper dimension_
$\mathrm{dim}^{+}(G)$, given by
$\mathrm{dim}^{+}(G)=\max_{R\in\mathcal{R}(G)}|R|$.

To generate sets in $\mathcal{R}(G)$, one could start with $R=V$, and
iteratively remove vertices while keeping $R$ resolving. In some cases,
starting with a smaller set is guaranteed to succeed as well. The _resolving
number_ of a graph, denoted $\mathrm{res}(G)$, is the smallest integer such
that all subsets $S\subset V$ with $|S|=\mathrm{res}(G)$ are resolving sets.
Combined with the above inequalities, we therefore have $\beta(G)\leq
dim^{+}(G)\leq\mathrm{res}(G)\leq n-1$ [17]. When
$k=\beta(G)=\mathrm{res}(G)$, every $R\in\mathcal{R}(G)$ with $|R|=k$ is
resolving and is of minimum size. In this case $G$ is said to be _randomly
$k$-dimensional_. The only known randomly $k$-dimensional graphs are $K_{k+1}$
and odd cycles $C_{n}$ with $n\geq 3$ and $k=2$. It is an open question as to
whether or not other types of randomly $k$-dimensional graphs exist [18].

##  9 Conclusion

Intuitively, metric dimension is a very simple idea. Its close relation to GPS
and trilateration in continuous space make applications concerning locating
nodes of graphs immediately clear. While determining the exact metric
dimension of general graphs is an NP-complete problem, a number of
approximation methods exist including the ICH algorithm. ICH gives small
resolving sets guaranteed to be close to optimal but has cubic run time, which
can be impractical for large networks. Fortunately, a great deal is known with
respect to exact formulae, asymptotic behavior, and bounds for an array of
graph families. Recently, the metric dimension of certain random graph models
like random trees and forests, Erdös-Rényi random graphs, and graphs generated
via the SBM have been characterized. Further work in this direction may lead
to a more complete understanding of metric dimension and of its behavior on
real-world networks.

This understanding is a critical step toward practical application in
different settings. These applications include identifying the source of a
spread in a network, detecting network motifs, and embedding symbolic data in
real space. Some of these applications make use of concepts related to metric
dimension allowing slightly different constraints, such as doubly resolving
sets and multilateration. Possible directions for future work abound, both in
deepening our theoretical understanding of metric dimension and related
concepts, and in applying these concepts in practice.

## Acknowledgements

This research was partially funded by NSF ISS grant No. 1836914. The authors
acknowledge the BioFrontiers Computing Core at the University of
Colorado–Boulder for providing High-Performance Computing resources (funded by
the NIH grant No. 1S10OD012300), supported by BioFrontiers IT group.

## References

  * [1] R. Arratia, L. Gordon, and M. S. Waterman, The Erdös-Rényi law in distribution, for coin tossing and sequence matching, The Annals of Statistics, (1990), pp. 539–570.
  * [2] L. Babai, Graph isomorphism in quasipolynomial time, in Proceedings of the 48th Annual ACM Symposium on Theory of Computing, 2016, pp. 684–697.
  * [3] L. Babai, P. Erdös, and S. M. Selkow, Random graph isomorphism, SIAM Journal on Computing, 9 (1980), pp. 628–635.
  * [4] M. Bača, E. T. Baskoro, A. Salman, S. Saputro, and D. Suprijanto, The metric dimension of regular bipartite graphs, Bulletin mathématique de la Société des Sciences Mathématiques de Roumanie, (2011), pp. 15–28.
  * [5] R. F. Bailey, J. Cáceres, D. Garijo, A. González, A. Márquez, K. Meagher, and M. L. Puertas, Resolving sets for johnson and kneser graphs, European Journal of Combinatorics, 34 (2013), pp. 736–751.
  * [6] L. Beaudou, P. Dankelmann, F. Foucaud, M. A. Henning, A. Mary, and A. Parreau, Bounding the order of a graph using its diameter and metric dimension: A study through tree decompositions and vc dimension, SIAM Journal on Discrete Mathematics, 32 (2018), pp. 902–918.
  * [7] R. Belmonte, F. V. Fomin, P. A. Golovach, and M. Ramanujan, Metric dimension of bounded width graphs, in International Symposium on Mathematical Foundations of Computer Science, Springer, 2015, pp. 115–126.
  * [8] P. Berman, B. DasGupta, and M.-Y. Kao, Tight approximability results for test set problems in bioinformatics, Journal of Computer and System Sciences, 71 (2005), pp. 145–162.
  * [9] B. Bollobás, D. Mitsche, and P. Pralat, Metric dimension for random graphs, The Electronic Journal of Combinatorics, 20 (2013).
  * [10] N. Booth and J. A. Matic, Mapping and leveraging influencers in social media to shape corporate brand perceptions, Corporate Communications: An International Journal, 16 (2011), pp. 184–191.
  * [11] J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo, and M. L. Puertas, On the metric dimension of infinite graphs, Electronic Notes in Discrete Mathematics, 35 (2009), pp. 15–20.
  * [12] J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara, and D. R. Wood, On the metric dimension of cartesian products of graphs, SIAM Journal on Discrete Mathematics, 21 (2007), pp. 423–441.
  * [13] Y.-D. Cai, K.-Y. Feng, Y.-X. Li, and K.-C. Chou, Support vector machine for predicting $\alpha$-turn types, Peptides, 24 (2003), pp. 629–630.
  * [14] M. Cha, H. Haddadi, F. Benevenuto, and K. P. Gummadi, Measuring user influence in twitter: The million follower fallacy, in Fourth International AAAI Conference on Weblogs and Social Media, 2010.
  * [15] G. Chartrand, L. Eroh, M. A. Johnson, and O. R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Applied Mathematics, 105 (2000), pp. 99–113.
  * [16] G. Chartrand, C. Poisson, and P. Zhang, Resolvability and the upper dimension of graphs, Computers & Mathematics with Applications, 39 (2000), pp. 19–28.
  * [17] , Resolvability and the upper dimension of graphs, Computers & Mathematics with Applications, 39 (2000), pp. 19–28.
  * [18] G. Chartrand and P. Zhang, On the chromatic dimension of a graph, Congressus Numerantium, (2000), pp. 97–108.
  * [19] , The theory and applications of resolvability in graphs, Congressus Numerantium, (2003), pp. 47–68.
  * [20] V. Chvátal, Mastermind, Combinatorica, 3 (1983), pp. 325–329.
  * [21] D. Conte, P. Foggia, C. Sansone, and M. Vento, Thirty years of graph matching in pattern recognition, International Journal of Pattern Recognition and Artificial Intelligence, 18 (2004), pp. 265–298.
  * [22] S. A. Cook, The complexity of theorem-proving procedures, in Proceedings of the Third Annual ACM Symposium on Theory of Computing, ACM, 1971, pp. 151–158.
  * [23] I. CPLEX, 9.1 documentation, Ilog Cplex Optimization Inc, (2005).
  * [24] H. Cramér, Sur un nouveau théoreme-limite de la théorie des probabilités, Actual. Sci. Ind., 736 (1938), pp. 5–23.
  * [25] M. Crasmaru, C. Glaßer, K. W. Regan, and S. Sengupta, A protocol for serializing unique strategies, in International Symposium on Mathematical Foundations of Computer Science, Springer, 2004, pp. 660–672.
  * [26] L. Davis, Handbook of genetic algorithms, Van Nostrand Reinhold, New York, 1991.
  * [27] J. Díaz, O. Pottonen, M. Serna, and E. J. Van Leeuwen, On the complexity of metric dimension, in European Symposium on Algorithms, Springer, 2012, pp. 419–430.
  * [28] P. Eichenberger, M. Fujita, S. T. Jensen, E. M. Conlon, D. Z. Rudner, S. T. Wang, C. Ferguson, K. Haga, T. Sato, J. S. Liu, et al., The program of gene transcription for a single differentiating cell type during sporulation in bacillus subtilis, PLoS Biol, 2 (2004), p. e328.
  * [29] D. Eppstein, Metric dimension parameterized by max leaf number, arXiv preprint arXiv:1506.01749, (2015).
  * [30] L. Epstein, A. Levin, and G. J. Woeginger, The (weighted) metric dimension of graphs: hard and easy cases, Algorithmica, 72 (2015), pp. 1130–1171.
  * [31] P. Erdös, F. Harary, and W. T. Tutte, On the dimension of a graph, Mathematika, 12 (1965), pp. 118–122.
  * [32] P. Erdös and A. Rényi, On two problems of information theory, Magyar Tud. Akad. Mat. Kutató Int. Közl, 8 (1963), pp. 229–243.
  * [33] M. Fehr, S. Gosselin, and O. R. Oellermann, The metric dimension of cayley digraphs, Discrete Mathematics, 306 (2006), pp. 31–41.
  * [34] M. Feng and K. Wang, On the metric dimension of bilinear forms graphs, Discrete Mathematics, 312 (2012), pp. 1266–1268.
  * [35] M. Feng, M. Xu, and K. Wang, On the metric dimension of line graphs, Discrete Applied Mathematics, 161 (2013), pp. 802–805.
  * [36] H. Fernau, P. Heggernes, P. van’t Hof, D. Meister, and R. Saei, Computing the metric dimension for chain graphs, Information Processing Letters, 115 (2015), pp. 671–676.
  * [37] F. Foucaud, G. B. Mertzios, R. Naserasr, A. Parreau, and P. Valicov, Identification, location–domination and metric dimension on interval and permutation graphs. i. bounds, Theoretical Computer Science, 668 (2017), pp. 43–58.
  * [38] , Identification, location-domination and metric dimension on interval and permutation graphs. ii. algorithms and complexity, Algorithmica, 78 (2017), pp. 914–944.
  * [39] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, WH Freeman and Company, New York, 1979.
  * [40] W. Goddard, Mastermind revisited, Journal of Combinatorial Mathematics and Combinatorial Computing, 51 (2004), pp. 215–220.
  * [41] O. Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, Apr. 2008.
  * [42] M. T. Goodrich, On the algorithmic complexity of the mastermind game with black-peg results, Information Processing Letters, 109 (2009), pp. 675–678.
  * [43] M. Gosak, R. Markovič, J. Dolenšek, M. S. Rupnik, M. Marhl, A. Stožer, and M. Perc, Network science of biological systems at different scales: A review, Physics of Life Reviews, 24 (2018), pp. 118–135.
  * [44] A. Grover and J. Leskovec, Node2vec: Scalable feature learning for networks, in Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2016, pp. 855–864.
  * [45] J. Guo, K. Wang, and F. Li, Metric dimension of some distance-regular graphs, Journal of Combinatorial Optimization, 26 (2013), pp. 190–197.
  * [46] V. Hähnke, M. Rupp, M. Krier, F. Rippmann, and G. Schneider, Pharmacophore alignment search tool: influence of canonical atom labeling on similarity searching, Journal of Computational Chemistry, 31 (2010), pp. 2810–2826.
  * [47] R. W. Hamming, Error detecting and error correcting codes, Bell Labs Technical Journal, 29 (1950), pp. 147–160.
  * [48] F. Harary and R. A. Melter, On the metric dimension of a graph, Ars Combinatoria, 2 (1976), p. 1.
  * [49] S. Hartung and A. Nichterlein, On the parameterized and approximation hardness of metric dimension, in 2013 IEEE Conference on Computational Complexity, IEEE, 2013, pp. 266–276.
  * [50] M. Hauptmann, R. Schmied, and C. Viehmann, Approximation complexity of metric dimension problem, Journal of Discrete Algorithms, 14 (2012), pp. 214–222.
  * [51] C. Hernando, M. Mora, I. M. Pelayo, C. Seara, J. Cáceres, and M. L. Puertas, On the metric dimension of some families of graphs, Electronic Notes in Discrete Mathematics, 22 (2005), pp. 129–133.
  * [52] C. Hernando, M. Mora, I. M. Pelayo, C. Seara, and D. R. Wood, Extremal graph theory for metric dimension and diameter, The Electronic Journal of Combinatorics, 17 (2010), p. 30.
  * [53] S. Hoffmann, A. Elterman, and E. Wanke, A linear time algorithm for metric dimension of cactus block graphs, Theoretical Computer Science, 630 (2016), pp. 43–62.
  * [54] J. Holland, Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence, University of Michigan Press, 1975.
  * [55] P. W. Holland and S. Leinhardt, The statistical analysis of local structure in social networks, tech. rep., National Bureau of Economic Research, 1974.
  * [56] J. Hu and X. Shang, Detection of network motif based on a novel graph canonization algorithm from transcriptional regulation networks, Molecules, 22 (2017), p. 2194.
  * [57] H. Iswadi, E. T. Baskoro, A. Salman, and R. Simanjuntak, The metric dimension of amalgamation of cycles, Far East Journal of Mathematical Sciences, 41 (2010), pp. 19–31.
  * [58] H. Iswadi, E. T. Baskoro, R. Simanjuntak, and A. Salman, The metric dimension of graph with pendant edges, The Journal of Combinatorial Mathematics and Combinatorial Computing, 65 (2008), pp. 139–145.
  * [59] M. Jannesari and B. Omoomi, The metric dimension of the lexicographic product of graphs, Discrete Mathematics, 312 (2012), pp. 3349–3356.
  * [60] I. Javaid, M. T. Rahim, and K. Ali, Families of regular graphs with constant metric dimension, Utilitas Mathematica, 75 (2008), pp. 21–34.
  * [61] Z. Jiang and N. Polyanskii, On the metric dimension of cartesian powers of a graph, Journal of Combinatorial Theory, Series A, 165 (2019), pp. 1–14.
  * [62] M. Johnson, Structure-activity maps for visualizing the graph variables arising in drug design, Journal of Biopharmaceutical Statistics, 3 (1993), pp. 203–236.
  * [63] M. Johnson, Browsable structure-activity datasets, Advances in Molecular Similarity, (1998), pp. 153–170.
  * [64] R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, Springer, 1972, pp. 85–103.
  * [65] Z. Katona, P. P. Zubcsek, and M. Sarvary, Network effects and personal influences: The diffusion of an online social network, Journal of Marketing Research, 48 (2011), pp. 425–443.
  * [66] S. Khuller, B. Raghavachari, and A. Rosenfeld, Landmarks in graphs, Discrete Applied Mathematics, 70 (1996), pp. 217–229.
  * [67] D. E. Knuth, The computer as master mind, Journal of Recreational Mathematics, 9 (1976), pp. 1–6.
  * [68] J. Kratica, Strong metric dimension: a survey, Yugoslav Journal of Operations Research, 24 (2016).
  * [69] J. Kratica, V. Kovačević-Vujčić, and M. Čangalović, Computing the metric dimension of graphs by genetic algorithms, Computational Optimization and Applications, 44 (2009), pp. 343–361.
  * [70] W. J. Krzanowski, Principles of multivariate analysis: A user’s perspective, OUP Oxford, 2000.
  * [71] V. Kumar and R. Mirchandani, Increasing the roi of social media marketing, MIT Sloan Management Review, 54 (2012), p. 55.
  * [72] L. Laird, R. C. Tillquist, S. Becker, and M. E. Lladser, Resolvability of Hamming graphs, SIAM Journal of Discrete Mathematics, 34 (2020), pp. 2063–2081.
  * [73] T. I. Lee, N. J. Rinaldi, F. Robert, D. T. Odom, Z. Bar-Joseph, G. K. Gerber, N. M. Hannett, C. T. Harbison, C. M. Thompson, I. Simon, et al., Transcriptional regulatory networks in saccharomyces cerevisiae, Science, 298 (2002), pp. 799–804.
  * [74] C. S. Leslie, E. Eskin, and W. S. Noble, The spectrum kernel: A string kernel for SVM protein classification., in Pacific Symposium on Biocomputing, vol. 7, Hawaii, USA, 2002, pp. 566–575.
  * [75] B. Lindström, On a combinatory detection problem I, I. Magyar Tud. Akad. Mat. Kutató Int. Közl, 9 (1964), pp. 195–207.
  * [76] A. Y. Lokhov, M. Mézard, H. Ohta, and L. Zdeborová, Inferring the origin of an epidemic with a dynamic message-passing algorithm, Physical Review E, 90 (2014), p. 012801.
  * [77] P. Manuel, R. Bharati, I. Rajasingh, and M. M. Chris, On minimum metric dimension of honeycomb networks, Journal of Discrete Algorithms, 6 (2008), pp. 20–27.
  * [78] P. Manuel, B. Rajan, I. Rajasingh, and M. C. Monica, Landmarks in torus networks, Journal of Discrete Mathematical Sciences and Cryptography, 9 (2006), pp. 263–271.
  * [79] P. D. Manuel, M. I. Abd-El-Barr, I. Rajasingh, and B. Rajan, An efficient representation of benes networks and its applications, Journal of Discrete Algorithms, 6 (2008), pp. 11–19.
  * [80] B. D. McKay and A. Piperno, Practical graph isomorphism, II, Journal of Symbolic Computation, 60 (2014), pp. 94–112.
  * [81] K. Meagher and R. F. Bailey, On the metric dimension of grassmann graphs, Discrete Mathematics & Theoretical Computer Science, 13 (2012).
  * [82] R. A. Melter and I. Tomescu, Metric bases in digital geometry, Computer Vision, Graphics, and Image Processing, 25 (1984), pp. 113–121.
  * [83] R. Meusel, S. Vigna, O. Lehmberg, and C. Bizer, Graph structure in the web—revisited: a trick of the heavy tail, in Proceedings of the 23rd International Conference on World Wide Web, ACM, 2014, pp. 427–432.
  * [84] D. Mitsche and J. Rué, On the limiting distribution of the metric dimension for random forests, European Journal of Combinatorics, 49 (2015), pp. 68–89.
  * [85] N. Mladenović, J. Kratica, V. Kovačević-Vujčić, and M. Čangalović, Variable neighborhood search for metric dimension and minimal doubly resolving set problems, European Journal of Operational Research, 220 (2012), pp. 328–337.
  * [86] C. Moore and M. E. Newman, Epidemics and percolation in small-world networks, Physical Review E, 61 (2000), p. 5678.
  * [87] M. E. Newman, Spread of epidemic disease on networks, Physical Review E, 66 (2002), p. 016128.
  * [88] R. Pastor-Satorras and A. Vespignani, Epidemic spreading in scale-free networks, Physical Review Letters, 86 (2001), p. 3200.
  * [89] P. C. Pinto, P. Thiran, and M. Vetterli, Locating the source of diffusion in large-scale networks, Physical Review Letters, 109 (2012), p. 068702.
  * [90] C. Poisson and P. Zhang, The dimension of unicyclic graphs, Journal of Combinatorial Mathematics and Combinatorial Computing, accepted, (2002).
  * [91] J. R. Quinlan, Induction of decision trees, Machine Learning, 1 (1986), pp. 81–106.
  * [92] B. Rajan, I. Rajasingh, J. A. Cynthia, and P. Manuel, Metric dimension of directed graphs, International Journal of Computer Mathematics, 91 (2014), pp. 1397–1406.
  * [93] B. Rajan, I. Rajasingh, and P. Manuel, On minimum metric dimension of circulant networks, Journal of Computer and Mathematical Sciences, 1 (2010), pp. 155–162.
  * [94] V. Saenpholphat and P. Zhang, Conditional resolvability in graphs: a survey, International Journal of Mathematics and Mathematical Sciences, 2004 (2004).
  * [95] S. Saputro, E. T. Baskoro, A. Salman, and D. Suprijanto, The metric dimensions of a complete n-partite graph and its cartesian product with a path, Journal of Combinatorial Mathematics and Combinatorial Computing, 71 (2009), p. 283.
  * [96] U. Schöning, Graph isomorphism is in the low hierarchy, Journal of Computer and System Sciences, 37 (1988), pp. 312–323.
  * [97] A. Sebő and E. Tannier, On metric generators of graphs, Mathematics of Operations Research, 29 (2004), pp. 383–393.
  * [98] D. Shah and T. Zaman, Rumors in a network: Who’s the culprit?, IEEE Transactions on Information Theory, 57 (2011), pp. 5163–5181.
  * [99] B. Shanmukha, B. Sooryanarayana, and K. Harinath, Metric dimension of wheels, Far East Journal of Applied Mathematics, 8 (2002), pp. 217–229.
  * [100] Z. Shen, S. Cao, W.-X. Wang, Z. Di, and H. E. Stanley, Locating the source of diffusion in complex networks by time-reversal backward spreading, Physical Review E, 93 (2016), p. 032301.
  * [101] S. S. Shen-Orr, R. Milo, S. Mangan, and U. Alon, Network motifs in the transcriptional regulation network of escherichia coli, Nature Genetics, 31 (2002), pp. 64–68.
  * [102] P. J. Slater, Leaves of trees, Congressus Numerantium, 14 (1975), p. 37.
  * [103] S. Söderberg and H. S. Shapiro, A combinatory detection problem, The American Mathematical Monthly, 70 (1963), pp. 1066–1070.
  * [104] B. Sooryanarayana, S. Kunikullaya, and N. N. Swamy, Metric dimension of generalized wheels, Arab Journal of Mathematical Sciences, 25 (2019), pp. 131–144.
  * [105] B. M. Spinelli, E. Celis, and P. Thiran, Observer placement for source localization: the effect of budgets and transmission variance, in 54th Annual Allerton Conference on Communication, Control, and Computing, 2016\.
  * [106] R. C. Tillquist, Low-Dimensional Embeddings for Symbolic Data Science, PhD thesis, University of Colorado, 2020.
  * [107] R. C. Tillquist, R. M. Frongillo, and M. E. Lladser, Truncated metric dimension for finite graphs, 2020.  In progress.
  * [108] R. C. Tillquist and M. E. Lladser, Low-dimensional representation of genomic sequences, Journal of Mathematical Biology, 79 (2019), pp. 1–29.
  * [109] R. D. Tillquist and M. E. Lladser, Multilateration of random networks with community structure, 2019.  ArXiv e-print identifier, arXiv:1911.01521.
  * [110] I. Tomescu and I. Javaid, On the metric dimension of the Jahangir graph, Bulletin Mathématique de la Société des Sciences Mathématiques de Roumanie, (2007), pp. 371–376.
  * [111] M. Trusov, A. V. Bodapati, and R. E. Bucklin, Determining influential users in internet social networks, Journal of Marketing Research, 47 (2010), pp. 643–658.
  * [112] C. von der Malsburg, Pattern recognition by labeled graph matching, Neural Networks, 1 (1988), pp. 141–148.
  * [113] K. Wagner, Über eine eigenschaft der ebenen komplexe, Mathematische Annalen, 114 (1937), pp. 570–590.
  * [114] T. Washio and H. Motoda, State of the art of graph-based data mining, ACM SIGKDD Explorations Newsletter, 5 (2003), pp. 59–68.
  * [115] I. Wegener, Complexity theory: exploring the limits of efficient algorithms, Springer Science & Business Media, 2005.
  * [116] D. Weininger, Smiles, a chemical language and information system. 1. introduction to methodology and encoding rules, Journal of Chemical Information and Computer Sciences, 28 (1988), pp. 31–36.
  * [117] X. Zhang, Y. Zhang, T. Lv, and Y. Yin, Identification of efficient observers for locating spreading source in complex networks, Physica A: Statistical Mechanics and its Applications, 442 (2016), pp. 100–109.