Discrete Applied Mathematics 105 (2000) 99–113

View metadata, citation and similar papers at core.ac.uk brought to you by CORE
provided by Elsevier - Publisher Connector
Resolvability in graphs and the metric dimension of a
graph
Gary Chartranda , Linda Eroha , Mark A. Johnsonb ,
Ortrud R. Oellermannc;∗;1
a Western
Michigan University, Kalamazoo, MI, 49008, USA
b Pharmacia
& Upjohn, Kalamazoo, MI, USA
c Department of Mathematics and Statistics, University of Winnipeg, 515 Portage Avenue, Winnipeg,

Canada, Man. R3B 2E9

Received 19 December 1998; revised 27 July 1999; accepted 24 January 2000

Abstract
For an ordered subset W = {w1 ; w2 ; : : : ; wk } of vertices in a connected graph G and a vertex
v of G, the metric representation of v with respect to W is the k-vector r(v | W ) = (d(v; w1 ),
d(v; w2 ); : : : ; d(v; wk )). The set W is a resolving set for G if r(u | W ) = r(v | W ) implies that
u = v for all pairs u; v of vertices of G. The metric dimension dim(G) of G is the minimum
cardinality of a resolving set for G. Bounds on dim(G) are presented in terms of the order
and the diameter of G. All connected graphs of order n having dimension 1; n − 2, or n − 1
are determined. A new proof for the dimension of a tree is also presented. From this result
sharp bounds on the metric dimension of unicyclic graphs are established. It is shown that
dim(H )6dim(H × K2 )6dim(H ) + 1 for every connected graph H . Moreover, it is shown
that for every positive real number , there exists a connected graph G and a connected induced
subgraph H of G such that dim(G)=dim(H ) ¡ . ? 2000 Elsevier Science B.V. All rights
reserved.

Keywords: Distance; Metric dimension; Basis

1. Introduction

The structure of a chemical compound is frequently viewed as a set of functional

groups arrayed on a substructure. From a graph-theoretic perspective, the structure is
a labeled graph where the vertex and edge labels specify the atom and bond types,
respectively. From this perspective, the functional groups and substructure are simply
subgraphs of the labeled graph representation. By changing the set of functional groups
∗ Corresponding author.

E-mail address: [email protected] (O.R. Oellermann).

1 Research supported by an NSERC grant Canada.

0166-218X/00/$ - see front matter ? 2000 Elsevier Science B.V. All rights reserved.
PII: S 0 1 6 6 - 2 1 8 X ( 0 0 ) 0 0 1 9 8 - 0
100 G. Chartrand et al. / Discrete Applied Mathematics 105 (2000) 99–113

and=or permuting their positions, a collection of compounds is essentially dened that

are characterized by the substructure common to them.
Traditionally, these “positions” simply re ect uniquely dened atoms (vertices) of
the substructure (common subgraph). These positions seldom form a minimum set in
the following sense. Let W be an ordered subset, of cardinality k say, of the vertex set
V (G) of the common subgraph G, and let v be a vertex in V (G). We can associate
with v an ordered k-tuple that gives the distances from v to each of the vertices in
W . Then the smallest such set W for which every two distinct vertices have distinct
ordered k-tuples forms a minimum dimensional representation of the positions denable
on the common subgraph. In this context, W is referred to as a resolving set relative
to V (G).
Under the traditional view, we can determine whether any two compounds in the
collection share the same functional group at a particular position. This comparative
statement plays a critical role in drug discovery whenever it is to be determined whether
the features of a compound are responsible for its pharmacological activity. However,
the statement, as it stands, is applicable only to compounds sharing the common sub-
graph G. By redening “position” to mean the value of an ordered k-tuple based on a
resolving set, the statement can be extended to broader collections of compounds. For
example, suppose that G is a subgraph of a graph H , and W is also a resolving set of
V (H ). Even though G and H dene two distinct collections with positions specied
by the same k-tuple, the comparative statement remains valid if one of the compounds
comes from the G-collection and the other comes from the H -collection. This ability to
extend the domain of such comparative statements motivates our interest in resolving
sets. In this paper we focus on the problem of determining the minimum cardinality
of a resolving set in a graph G relative to V (G).

2. Resolvable sets in graphs

The ideas discussed in Section 1 suggest some mathematical concepts, which we now
describe. We denote the standard distance between two vertices u and v in a connected
graph G by d(u; v). By an ordered set of vertices, we mean a set W = {w1 ; w2 ; : : : ; wk }
on which the ordering (w1 ; w2 ; : : : ; wk ) has been imposed. For an ordered subset W =
{w1 ; w2 ; : : : ; wk } of V (G), we refer to the k-vector (ordered k-tuple)
r(v | W ) = (d(v; w1 ); d(v; w2 ); : : : ; d(v; wk ))
as the (metric) representation of v with respect to W. The set W is called a resolving
set for G if r(u | W ) = r(v | W ) implies that u = v for all u, v ∈ V (G). Hence if W
is a resolving set of cardinality k for a graph G of order n, then the set {r(v | W ) | v
∈ V (G)} consists of n distinct k-vectors. A resolving set of minimum cardinality for
a graph G is called a minimum resolving set.
For example, consider the graph G of Fig. 1. The set W1 = {v1 ; v3 } is not a resolving
set for G since r(v2 | W1 ) = (1; 1) = r(v4 | W1 ). On the other hand, W2 = {v1 ; v2 ; v3 } is a
 G. Chartrand et al. / Discrete Applied Mathematics 105 (2000) 99–113 101

Fig. 1.

resolving set for G since the representations for the vertices of G with respect to W2
are
r(v1 | W2 ) = (0; 1; 1); r(v2 | W2 ) = (1; 0; 1); r(v3 | W2 ) = (1; 1; 0):
r(v4 | W2 ) = (1; 2; 1); r(v5 | W2 ) = (2; 1; 1);
However, W2 is not a minimum resolving set since W3 = {v1 ; v2 } is also a resolving
set. Since no single vertex constitutes a resolving set for G, it follows that W3 is a
minimum resolving set.
We now return to our discussion of the classication problem in chemistry. A fun-
damental problem in the study of chemical structures is to determine ways to represent
a set of chemical compounds such that distinct compounds have distinct representa-
tions. One way to accomplish this is rst to associate a graph with each compound
(which can be done quite naturally) and dene an integer-valued metric on the set of
corresponding graphs such that the distance between some pairs of graphs is 1. Next
a metagraph G is constructed whose vertices are these graphs, where two vertices are
adjacent in G if and only if the distance between their corresponding graphs is 1. Then
the representations of the vertices of G are computed with respect to some minimum
resolving set of G, thereby providing representations of the compounds as well.
The idea of resolving sets and minimum resolving sets has appeared in the literature
previously. In [4] and later in [5], Slater introduced the concept of a resolving set for
a connected graph G under the term locating set. He referred to a minimum resolving
set as a reference set for G. He called the cardinality of a minimum resolving set
(reference set) the location number of G. Slater described the usefulness of these
ideas when working with sonar and loran stations. Independently, Harary and Melter
[2] discovered these concepts as well but used the term metric dimension, rather than
location number. We adopt the terminology of Harary and Melter. Consequently, the
metric dimension or, more simply, the dimension dim(G) of a connected graph G
is the cardinality of a minimum resolving set. Because of the suggestiveness of this
terminology to linear algebra, we also refer to a minimum resolving set as a basis
for G. Hence, the vertices of G have distinct representations with respect to the basis
vertices. For the graph G of Fig. 1, dim(G) = 2 and {v1 ; v2 } is a basis for G. It was
noted in [1, p. 204] that determining the metric dimension of a graph is an NP-complete
problem.
We next describe the problem of nding the metric dimension and a basis for a
graph in terms of an integer programming problem. Let G be a connected graph of
102 G. Chartrand et al. / Discrete Applied Mathematics 105 (2000) 99–113

order n with V (G) = {v1 ; v2 ; : : : ; vn } and let D = [dij ] be the distance matrix of G, that
is, dij = d(vi ; vj ) for 16i; j6n. For xi ∈ {0; 1} for 16i6n, dene the function F by
F(x1 ; x2 ; : : : ; x n ) = x1 + x2 + · · · + x n :


Minimizing F subject to the n2 constraints
|di1 –dj1 |x1 + |di2 –dj2 |x2 + · · · + |din –djn |x n ¿ 0 for 16i ¡ j6n
is equivalent to nding a basis in the sense that if x10 ; x20 ; : : : ; xn0 is a set of values for
which F attains its minimum, then W = {vi | xi0 = 1} is a basis for G, and, conversely,
if W = {vi1 ; vi2 ; : : : ; vin } is a basis for G and if we dene

0 1 if s = ij for some j (16j6k)
xs =
0 otherwise
then F(x10 ; x20 ; : : : ; xn0 ) is a minimum subject to the given constraints.
Notice, for each connected graph G and each ordered set W = {w1 ; w2 ; : : : ; wk } of
vertices of G, that the ith coordinate of r(wi | W ) is 0 and that the ith coordinate of
all other vertex representations is positive. Thus, certainly r(u | W ) = r(v | W ) implies
that u = v for u ∈ W . Therefore, when testing whether an ordered subset W of V (G)
is a resolving set for G, we need only be concerned with the vertices of V (G) − W .
Consequently, V (G) and V (G) − {v} are resolving sets for every nontrivial connected
graph G and every vertex v of G. As a result, if G is a connected graph of order n¿2,
then 16dim(G)6n − 1. On the other hand, if we know the diameter of G, then we
can obtain an improved upper bound in general for dim(G), as well as a lower bound.
For positive integers d and n, we dene f(n; d) to be the least positive integer k for
which k + dk ¿n.

Theorem 1. If G is a connected graph of order n¿2 and diameter d; then

f(n; d)6dim(G)6n − d:

Proof. First, we establish the upper bound. Let u and v be vertices of G for which
d(u; v) = d, and let u = v0 ; v1 ; : : : ; vd = v be a u–v path of length d. Let W = V (G)
− {v1 ; v2 ; : : : ; vd }. Since d(u; vi ) = i for 16i6d and u ∈ W , it follows that W is a
resolving set of cardinality n − d for G. Thus, dim(G)6n − d.
Next, we consider the lower bound. Let B be a basis for G of dimension k. Since
each representation of a vertex of V (G) − B is a k-vector, every coordinate of which is
a positive integer not exceeding d, and all n − k representations are distinct, it follows
that dk ¿n − k. Hence, f(n; d)6k = dim(G).

The inequality given in the upper bound of Theorem 1 can be strict. For example,
the tree T1 of Fig. 2 has order n = 8 and diameter d = 4, but B1 = {v1 ; v8 } is a basis
for T1 and so dim(T1 ) = 2 and n − d = 4. On the other hand, the tree T2 of Fig. 2
shows that the upper bound in Theorem 1 can be sharp since T2 also has order n = 8
and diameter d = 4, while B2 = {w1 ; w6 ; w7 ; w8 } is a basis and so dim(T2 ) = 4.
 G. Chartrand et al. / Discrete Applied Mathematics 105 (2000) 99–113 103

Fig. 2.

Fig. 3.

The lower bound in Theorem 1 can be attained for graphs of diameter 2 or 3. For
example, the graph G1 of Fig. 3 has order 6, diameter 2, and dimension f(6; 2) = 2.
Also, the graph G2 of Fig. 3 has order 11, diameter 3, and dimension f(11; 3) = 2.
The vertices of both graphs in Fig. 3 are lableled with their representations.
On the other hand, if d = dim(G)¿4 and dim(G)¿2, then the lower bound given
in Theorem 1 cannot be sharp. To see this, suppose, to the contrary, that there ex-
ists a graph G of order n, diameter d, and dim(G) = k such that k + dk = n. Let
W be a basis for G. Then all k-tuples of positive integers not exceeding d must ap-
pear as a representation of some vertex of G with respect to W . However, since the
k-vector (1; 1; : : :) appears, it follows that d(w1 ; w2 )62. For some vertex v of G; r(v | W )
= (1; 4; : : :). Thus, d(v; w1 ) = 1, but
d(v; w2 ) = 4 ¿ 1 + 2¿d(v; w1 ) + d(w1 ; w2 );
which is impossible; so no such graph exists.
If G = Pn , then by Theorem 1, dim(G) = 1 and either end-vertex of G constitutes a
basis. Indeed, as we next show, paths are the only graphs of dimension 1.

Theorem 2. A connected graph G of order n has dimension 1 if and only if G = Pn .

Proof. We have already noted that if G=Pn , then dim(G)=1. For the converse, assume
that G is a connected graph with dim(G) = 1 and basis W = {w}. For each vertex v of
G; r(v | W ) = d(v; w) is a nonnegative integer less than n. Since the representations of
the vertices of G with respect to W are distinct, there exists a vertex u of G such that
d(u; w) = n − 1. Consequently, the diameter of G is n − 1, which implies that G = Pn .
104 G. Chartrand et al. / Discrete Applied Mathematics 105 (2000) 99–113

On the other hand, consider G=Kn ; n¿2, and let W be a basis for G. If u 6∈ W , then
every coordinate of r(u | W ) is 1. Therefore, every resolving set for G must contain
all but one vertex of G, so dim(Kn ) = n − 1. By Theorem 1, if G is a connected graph
that is not complete, then dim(G)6n − 2. Hence, we have the following result.

Theorem 3. A connected graph G of order n¿2 has dimension n − 1 if and only if

G = Kn .

3. Graphs with dimension n − 2

In Theorem 3, we characterized those graphs of order n having dimension n − 1.

Indeed, these are precisely the complete graphs. In this section, we classify those graphs
of order n with dimension n − 2. For graphs G and H we use G ∪ H to denote the
disjoint union of G and H and G + H to denote the graph obtained from the disjoint
union of G and H by joining every vertex of G with every vertex of H .

Theorem 4. Let G be a connected graph of order n¿4. Then dim(G) = n − 2 if and

only if G = Ks; t (s; t¿1); G = Ks + Kt (s¿1; t¿2); or G = Ks + (K1 ∪ Kt ) (s; t¿1).

Proof. Each of the graphs mentioned in the statement of the theorem has dimension
n−2. To see this, note that if the vertices of a graph are partitioned as V1 ∪V2 ∪· · ·∪Vp
where either Vi is independent and its vertices have identical open neighborhoods or
Vi induces a clique and its vertices have identical closed neighborhoods, then the
dimension is at least ( | V1 | − 1) + ( | V2 | − 1) + · · · + ( | Vp | − 1).
For the converse, assume that G is a connected graph of order n¿4 such that
dim(G) = n − 2. By Theorems 1 and 3, it follows that G has diameter 2. If G is
bipartite, then since the diameter of G is 2, G = Ks; t for some integers s; t¿1. Hence,
we may assume that G is not bipartite. Therefore, G contains an odd cycle. Let Cr
be a smallest odd cycle in G. We claim that r = 3. Certainly, Cr is an induced cycle
of G. If G contains an induced k-cycle v1 ; v2 ; : : : ; vk ; v1 , where k¿5, then W = V (G)
− {v2 ; v3 ; v4 } is a resolving set of cardinality n − 3, for if we let w1 = v1 and w2 = v5 ,
then r(v2 | W ) = (1; s; : : :); r(v3 | W ) = (2; 2; : : :), and r(v4 | W ) = (t; 1; : : :) where s; t¿2.
Hence, dim(G)6n − 3, which is a contradiction. Thus G has no induced cycle of
length k ¿ 5 and so r = 3 and G contains a triangle.
Let Y be the vertex set of a maximum clique of G. Since G contains a triangle,
| Y | ¿3. Let U = V (G) − Y . Since G is not complete, | U | ¿1. If | U | = 1, then
G = Ks + (K1 ∪ Kt ) for some integers s and t. Now, s¿1 since G is connected and
t¿1 since G is not complete. From these observations, we may assume that | U | ¿2.
First, we show that U is an independent set of vertices. Suppose, to the contrary,
that U is not independent. Then U contains two adjacent vertices u and w. Because
of the dening property of Y , there exist v ∈ Y such that uv 6∈ E(G) and v0 ∈ Y such
that wv0 6∈ E(G), where v and v0 are not necessarily distinct. We consider two cases.
 G. Chartrand et al. / Discrete Applied Mathematics 105 (2000) 99–113 105

Fig. 4.

Fig. 5.

Case 1: There exists a vertex v ∈ Y such that uv; wv 6∈ E(G). We now consider
two subcases.
Subcase 1.1: There exists a vertex x ∈ Y that is adjacent to exactly one of u and
w, say u. Since | Y | ¿3, there exists a vertex y ∈ Y that is distinct from v and x.
Thus G contains the subgraph shown in Fig. 4, where dotted lines indicate that the
given edge is not present.
Let W = V (G) − {u; w; y}. Letting w1 = v and w2 = x, we have
r(u | W ) = (2; 1; : : :);

r(w | W ) = (2; 2; : : :);

r(y | W ) = (1; 1; : : :):

So W is a resolving set of cardinality n − 3, which is a contradiction.
Subcase 1.2: Every vertex of Y is adjacent to either both u and w or to neither
u nor w. If u and w are adjacent to every vertex in Y − {v}, then the vertices of
(Y − {v}) ∪ {u; w} are pairwise adjacent, contradicting the dening property of Y .
Thus, there exists a vertex y ∈ Y such that y is distinct from v, and y is adjacent to
neither u nor w.
Since the diameter of G is 2, there is a vertex x of G that is adjacent to both u and
v. Thus, G contains the subgraph shown in Fig. 5, where dotted lines indicate that the
given edges are not in G.
Let W = V (G) − {x; y; w} and label w1 = v and w2 = u. Then
r(x | W ) = (1; 1; : : :);

r(y | W ) = (1; 2; : : :);

r(w | W ) = (2; 1; : : :):

Thus, W is a resolving set of cardinality n − 3, producing a contradiction.
106 G. Chartrand et al. / Discrete Applied Mathematics 105 (2000) 99–113

Fig. 6.

Fig. 7.

Case 2: For each vertex v of Y; v is adjacent to at least one of u and w. Because

Y is the vertex set of a maximum clique, there exist vertices v; v0 ∈ Y such that
uv; wv0 6∈ E(G). Necessarily, vw; v0 u ∈ E(G). Since | Y | ¿3, there exists a vertex y in
Y distinct from v and v0 . Now, at least one of the edges yu and yw must be present in
G, say yu. Thus, G contains the subgraph shown in Fig. 6, where again dotted edges
indicate that the given edge is not in G.
Let W = V (G) − {u; w; y} and label w1 = v and w2 = v0 . Then
r(u | W ) = (2; 1; : : :);

r(w | W ) = (1; 2; : : :);

r(y | W ) = (1; 1; : : :):

Again, W is a resolving set of cardinality n − 3, which is a contradiction. Thus, as
claimed, U is independent.
Next, we claim that N (u) = N (w) for all u; w ∈ U . Let u and w be any two vertices
of U . Suppose that uv ∈ E(G) for some vertex v of G. Necessarily, v ∈ Y . We show
that wv ∈ E(G). Assume, to the contrary, that wv 6∈ E(G). Since Y is the vertex set
of a maximum clique, there exists y ∈ Y such that uy 6∈ E(G). Since G is connected
and U is independent, w is adjacent to some vertex of Y . If w is adjacent only to y,
then since w and y are not adjacent to u; d(w; u) = 3, which contradicts the fact that
the diameter of G is 2. Thus there exists a vertex x in Y distinct from y such that
wx ∈ E(G). Therefore, G contains the subgraph shown in Fig. 7, where again dotted
edges are not in G.
Let W = V (G) − {u; w; x} and label w1 = v and w2 = y. Then
r(u | W ) = (1; 2; : : :);

r(w | W ) = (2; : : :);

r(x | W ) = (1; 1; : : :):

Thus, W is a resolving set of cardinality n − 3, producing a contradiction.
 G. Chartrand et al. / Discrete Applied Mathematics 105 (2000) 99–113 107

Fig. 8.

Therefore, V (G) = Y ∪ U , where Y induces a clique, U is independent, | Y | ¿3;

| U | ¿2, and N (u) = N (w) for all u; w ∈ U .
Next, we claim that for u ∈ U , there is at most one vertex of Y not contained in
N (u). Suppose, to the contrary, that there are two vertices x; y ∈ Y not in N (u). Let w
be a vertex of U that is distinct from u. Therefore, N (w)=N (u). Since G is connected,
there exists z ∈ Y such that z ∈ N (u) = N (w). Thus, G contains the subgraph shown
in Fig. 8, where dotted edges are not edges of G.
Let W = V (G) − {y; w; z} and label w1 = x and w2 = u. Then
r(y | W ) = (1; 2; : : :);

r(w | W ) = (2; 2; : : :);

r(z | W ) = (1; 1; : : :):

So W is a resolving set of cardinality n − 3, producing a contradiction.
Now, N (u) = Y or N (u) = Y − {v} for some v ∈ Y . If N (u) = Y , then G = Ks + Kt
for s = | Y | ¿3 and t = | U | ¿2. If N (u) = Y − {v}, then G = Ks + (K1 ∪ Kt ), where
V (K1 ) = {v}; s = | Y | − 1¿2, and t = | U | ¿2. However, Ks + (K1 ∪ Kt ) = Ks + Kt+1 .
In either case, G is the join of a complete graph and an empty graph.

4. The dimensions of trees and unicylic graphs

In Theorem 2, we noted that the dimension of the path Pn (n¿2) is 1. By Theorem

4, the dimension of the star K1; n−1 (n¿3) of order n is n − 2. Indeed, for every tree
T of order n¿3; 16dim(T )6n − 2. In this section, we present a formula for the
dimension of trees that are not paths as well as bounds for the dimension of unicyclic
graphs. The formula for trees has also been established by Slater [4] and Harary and
Melter [2]. The proof we include here uses ideas dierent to those used in these two
papers. First, a few denitions are in order.
A vertex of degree at least 3 in a graph G will be called a major vertex of G.
Any end-vertex u of G is said to be a terminal vertex of a major vertex v of G if
d(u; v) ¡ d(u; w) for every other major vertex w of G. The terminal degree ter(v) of
a major vertex v is the number of terminal vertices of v. A major vertex v of G is an
exterior major vertex of G if it has positive terminal degree. Let (G) denote the sum
of the terminal degrees of the major vertices of G, and let ex(G) denote the number
of exterior major vertices of G.
108 G. Chartrand et al. / Discrete Applied Mathematics 105 (2000) 99–113

The following lemma which holds for general graphs will be used in the proofs of
the next two theorems.

Lemma 1. If G is a graph; then dim(G)¿(G) − ex(G).

Proof. Let W be any resolving set and let v be an exterior major vertex of G. Let
k = ter(v) and let u1 ; u2 ; : : : ; uk denote the terminal vertices of v. Thus the branch of G
at v containing ui (16i6k) is a v–ui path Qi . We claim that W contains at least one
vertex from each of the paths Qi –v (16i6k) with at most one exception. Suppose, to
the contrary, that two of these paths contain no vertex of W , say Q1 –v and Q2 –v. Let
u10 and u20 be the vertices adjacent to v on Q1 and Q2 , respectively. Since neither Q1 –v
nor Q2 –v contains a vertex of W , it follows that r(u10 | W ) = r(u20 | W ); contradicting
the fact that W is a resolving set. Thus, as claimed, W contains at least one vertex
from each of the paths Qi –v (16i6k) with at most one exception. Consequently,
dim(G)¿(G) − ex(G).

Theorem 5. If T is a tree that is not a path; then

dim(T ) = (T ) − ex(T ):

Proof. By Lemma 1, dim(T )¿(T ) − ex(T ):

We now verify the reverse inequality. We construct a set W of vertices of T by

placing every terminal vertex, except one, of each exterior major vertex of T in W .
We claim that W is a resolving set of T . In order to see this, let u be an arbitrary
vertex of T . We consider two cases.
Case 1: Suppose that there is some exterior major vertex w of T and a terminal
vertex x of w such that u lies on the w–x path of T. We now consider two subcases.
Subcase 1.1: Suppose that x ∈ W . Let v be any vertex of T dierent from u. If v
lies on the u–x path of T , then d(v; x) ¡ d(u; x); otherwise, d(u; x) ¡ d(v; x): In either
case, r(u | W ) 6= r(v | W ):
Subcase 1.2: Suppose that x 6∈ W . Let v be any vertex of T dierent from u. If
there is some vertex y in W such that either v lies on the u–y path of T or u lies on
the v–y path, then d(v; y) ¡ d(u; y) or d(u; y) ¡ d(v; y); respectively. In either case,
r(u | W ) 6= r(v | W ). Thus, we may assume that every path between v and a vertex
of W does not contain u and that every path between u and a vertex of W does not
contain v. Necessarily, then, there exists an exterior major vertex w0 and a terminal
vertex x0 of w0 such that v lies on the w0 –x0 path of T and v 6= w0 . Moreover, x0 6∈ W
and u 6= w: Note that w 6= w0 , for otherwise either x or x0 belongs to W .
Since the degrees of both w and w0 are at least 3, there exists a branch B at w that
contains neither w0 nor x and there is a branch B0 at w0 that contains neither w nor x0 .
Necessarily, both B and B0 must contain a vertex of W . Let z and z 0 be vertices of
W belonging to B and B0 , respectively. If d(u; z 0 ) 6= d(v; z 0 ); then r(u | W ) 6= r(v | W );
so we may assume that d(u; z 0 ) = d(v; z 0 ). In this case, d(u; z) ¡ d(v; z); implying that
r(u | W ) 6= r(v | W ).
 G. Chartrand et al. / Discrete Applied Mathematics 105 (2000) 99–113 109

Case 2: Suppose, for every exterior major vertex w of T and every terminal vertex
x of w, that u does not lie on the w–x path of T. Then there are at least two branches
at u, say B and B0 , each of which contains some exterior major vertex of terminal
degree at least 2. Therefore, each of B and B0 contains a vertex of W . Let z and
z 0 be vertices of W in B and B0 , respectively. Let v be a vertex of T distinct from
u. If v belongs to B, then the v–z 0 path of T contains u; so d(u; z 0 ) ¡ d(v; z 0 ) and
r(u | W ) 6= r(v | W ). If v does not belong to B, then the v–z path of T contains u.
Hence d(u; z) ¡ d(v; z) and so r(u | W ) 6= r(v | W ):
Hence W is a resolving set of T and dim(T )6|W | = (T ) − ex(T ):

It is often of interest to know how the value of a graphical parameter is aected

when a small change is made in a graph. In this context, we answer the question
in the case of dimension when a single edge is added to a tree. We show, in fact,
that the dimension can increase by at most 1 or decrease by at most 2 and that all
values in this range are attainable. Since the proof of this result is similar to that of
Theorem 5, we only provide a detailed outline of its proof.

Theorem 6. If T is a tree of order at least 3 and e is an edge of T ; then

dim(T ) − 26dim(T + e)6dim(T ) + 1:

Proof. Since (T + e)¿(T ) − 2 and ex(T + e)6ex(T ); it follows that

(T + e) − ex(T + e)¿(T ) − ex(T ) − 2 = dim(T ) − 2:

By Lemma 1, dim(T + e)¿(T + e) − ex(T + e). From this it follows that dim(T + e)
¿dim(T ) − 2:
It remains to show then that dim(T + e)6dim(T ) + 1: Let W be a set of vertices
of T + e that contains for each exterior major vertex v of T + e, all terminal vertices v
with one exception. Let C denote the unique cycle of T + e. We consider four cases.
Case 1: C contains at least three major vertices, each of which has a branch
containing a vertex of W. In this case W is a resolving set for T +e and so dim(T +e)
6|W |6dim(T ):
Case 2: C contains exactly two major vertices v and w, each of which has a branch
containing a vertex of W. Let u be a vertex of C distinct from v and w. In this case,
W ∪ {u} is a resolving set for T + e; so dim(T + e)6|W | + 16dim(T ) + 1.
Case 3: C contains exactly one major vertex v that has a branch containing a
vertex of W. Let H be the branch of T + e that contains C. Except possibly for v,
every vertex of H has degree at least 3 in T + e. Since at least one vertex of H
has terminal degree in T one greater than its terminal degree in T + e; it follows that
(T ) − ex(T ) = |W | + 1: Let W 0 denote the set obtained by adding to W two vertices
of C that are distinct from v. Then W 0 is a resolving set for T + e and

dim(T + e)6|W 0 | = |W | + 26(T ) − ex(T ) + 1 = dim(T ) + 1:

110 G. Chartrand et al. / Discrete Applied Mathematics 105 (2000) 99–113

Case 4: There is no major vertex belonging to C that has a branch containing a

vertex of W. Thus W =∅. In this case, T is a caterpillar with maximum degree at most
3. If T is not a path, then dim(T )=2 and any three vertices of C constitute a resolving
set for T + e. Hence dim(T + e)6dim(T ) + 1. On the other hand, if T is a path, then
dim(T ) = 1. Let W 0 be the set consisting of the two end-vertices of T . Then W 0 is a
resolving set for T + e for every possible choice of e and so dim(T + e)6dim(T ) + 1.

By Theorem 6, if T is a tree of order at least 3 and e is an edge of T ; then

dim(T + e) = dim(T ) + k for some k ∈ {−2; −1; 0; 1}. We show that for each such k,
there exists a tree T and an edge e of T such that dim(T + e) = dim(T ) + k:
(1) k = −2. Let T be the tree obtained by subdividing the central edge of a double
star having two major vertices u and v. Let u1 be an end-vertex adjacent to u and v1
an end-vertex adjacent with v. Then dim(T + u1 v1 ) = dim(T ) − 2:
(2) k = −1. Let T be the tree dene in (1). Then dim(T + uv1 ) = dim(T ) − 1:
(3) k=0. Let T be a star containing end-vertices x and y. Then dim(T +xy)=dim(T ):
(4) k = 1. Let T be a path containing nonadjacent vertices w and z. Then dim(T
+ wz) = dim(T ) + 1:
When an edge is added to a tree the result is of course a unicyclic graph G (a con-
nected graph containing exactly one cycle). Using dierent parameters and a dierent
approach, Poisson and Zhang [3] established upper and lower bounds for dim(G) and
showed that a range of four values is possible, which is consistent with Theorem 6.

5. The dimension of the product H × K2

In this section we show, for each connected graph H , that the dimension of the
cartesian product H × K2 is either dim(H ) or dim(H ) + 1; where the cartesian product
of two graphs G and H is dened as the graph with vertex set V (G) × V (H ) and edge
set {(u; v)(x; y) | u = x and vy ∈ E(H ) or v = y and ux ∈ E(G)}.

Theorem 7. For every connected graph H;

dim(H )6dim(H × K2 )6dim(H ) + 1:

Proof. First, we establish the upper bound. Let G = H × K2 where H1 and H2 are
the two copies of H in G. Let W be a basis for H and let W1 = {w1 ; w2 ; : : : ; wk } and
W2 = {u1 ; u2 ; : : : ; uk } be the bases of H1 and H2 , respectively, corresponding to W . We
claim that U = W1 ∪ {u1 } is a resolving set for G.
Let x and y be vertices of G such that r(x | U ) = r(y | U ). We show that x = y. This
is certainly the case if x or y belongs to U . Thus we may assume that x; y 6∈ U . We
consider three cases.
Case 1: Both x and y belong to H1 . Then dG (x; wi ) = dH1 (x; wi ) and dG (y; wi )
= dH1 (y; wi ) for i = 1; 2; : : : ; k. Suppose that x 6= y. Since W is a resolving set
 G. Chartrand et al. / Discrete Applied Mathematics 105 (2000) 99–113 111

for H1 , it follows that dH1 (x; wi ) 6= dH1 (y; wi ) for some i (16i6k): Hence, dG (x; wi ) 6=
dG (y; wi ); which contradicts the fact that r(x | U ) = r(y | U ). Therefore, x = y.
Case 2: Either x ∈ V (H1 ) and y ∈ V (H2 ); or x ∈ V (H2 ) and y ∈ V (H1 ), say
the former. In this case, dG (x; u1 ) = dG (x; w1 ) + 1 and dG (y; u1 ) = dG (y; w1 ) − 1.
Thus, either dG (x; u1 ) 6= dG (y; u1 ) or dG (x; w1 ) 6= dG (y; w1 ), contradicting the fact that
r(x | U ) = r(y | U ): Thus x = y:
Case 3: Both x and y belong to H2 . First, suppose that at least one of x and y
belongs to W , say x ∈ W: Then x = ui for some i (16i6k); so dG (x; wi ) = 1: Since
r(x | U )=r(y | U ); it follows that dG (y; wi )=1. However, the only vertex in H2 adjacent
to wi is ui ; so y = ui = x:
For x; y 6∈ U , let x0 and y0 be the vertices in H1 corresponding to x and y, respec-
tively. As in Case 1, if x0 6= y0 , then dG (x0 ; wi ) 6= dG (y0 ; wi ) for some i (16i6k).
Now, dG (x; wi )=dG (x0 ; wi )+1 and dG (y; wi )=dG (y0 ; wi )+1; so dG (x0 ; wi )=dG (y0 ; wi ),
which implies that x0 = y0 and, consequently, that x = y.
Now, we establish the lower bound stated in the theorem. Again, let G = H × K2 ,
where H1 and H2 are the two copies of H in G. Let Vi be the vertex set of Hi for
i=1; 2: Thus V (G)=V1 ∪V2 . Let W be a basis for G, with W1 =W ∩V1 and W2 =W ∩V2 .
Let U1 ⊆ V (H1 ) be the union of W1 and the set W20 consisting of those vertices of V1
corresponding to W2 . Thus,
|U1 | = |W1 ∪ W20 |6|W1 | + |W20 | = |W |:
We claim that U1 is a resolving set for H1 .
Let u and v be distinct vertices of H1 . We show that r(u | U1 ) 6= r(v | U1 ). If either
u or v belongs to W1 , then this is certainly the case. Otherwise, there exists a vertex
w ∈ W such that dG (u; w) 6= dG (v; w). If w ∈ V1 , then dH1 (u; w) = dG (u; w) 6=
dG (v; w) = dH1 (v; w). If w ∈ V2 , then let w0 be the vertex of U1 corresponding to w. So
dH1 (u; w0 )=dG (u; w)−1 6= dG (v; w)−1=dH1 (v; w0 ). In either case, r(u | U1 ) 6= r(v | U1 ):

It is possible to have equality in either bound in Theorem 7. For example, if

H = K3 , then dim(H ) = dim(H × K2 ) = 2; while if H = C4 , then dim(H ) = 2 and
dim(H × K2 ) = 3. Referring to this last example we see that a simple inductive argu-
ment yields dim(Qn )6n for n¿2. We know, in fact, that dim(Qn ) = n for 26n64:
Of course, H is an induced subgraph of H × K2 , and Theorem 7 states that
dim(H × K2 )
¿1:
dim(H )
By choosing the integer m to be arbitrarily large and by letting G =K1; m and H =K2 ,
we see that we can make the ratio dim(G)=dim(H ) as large as we wish, where H is
an induced subgraph of G. Although this may not be surprising, it may be unexpected
that, in fact we can make dim(G)=dim(H ) as small as we wish, where H is an induced
subgraph of G. We now verify the truth of this statement.
Let n¿3 be an integer. Label the vertices of the star K1; 2n+1 with v0 ; v1 ; v2 ; : : : ; v2n ; v10 ;
v20 ; : : : ; v20 n , where v0 is the central vertex. Then we add two new vertices x and x0 and
112 G. Chartrand et al. / Discrete Applied Mathematics 105 (2000) 99–113

Fig. 9.

the 2n+1 edges xvi and x0 vi0 for 16i62n . Next we add two sets W = {w1 ; w2 ; : : : ; wn }
and W 0 ={w10 ; w20 ; : : : ; wn0 } of vertices, together with the edges wi x and wi0 x0 for 16i6n.
Finally we add edges between W and {v1 ; v2 ; : : : ; v2n } so that each of the 2n possible
n-tuples of 1’s and 2’s appears exactly once as r(vi | W ) for 16i62n . Similarly, edges
are added between W 0 and {v10 ; v20 ; : : : ; v20 n } so that the representations r(vi0 | W 0 ) are
distinct for 16i62n . Denote the resulting graph by G. The graph G for n = 3 is
shown in Fig. 9.
We claim that W ∪ W 0 is a resolving set for G. By construction, r(vi | W ∪ W 0 )
= r(vj | W ∪ W 0 ) implies that i = j, and r(vi0 | W ∪ W 0 ) = r(vj0 | W ∪ W 0 ) implies that
i = j. Observe that
r(x | W ∪ W 0 ) = (1; 1; : : : ; 1; 4; 4; : : : ; 4);
r(vi | W ∪ W 0 ) = (−; −; : : : ; −; 3; 3; : : : ; 3); 16i62n ;
r(v0 | W ∪ W 0 ) = (2; 2; : : : ; 2; 2; 2; : : : ; 2);
r(vi0 | W ∪ W 0 ) = (3; 3; : : : ; 3; −; −; : : : ; −); 16i62n ;
r(x0 | W ∪ W 0 ) = (4; 4; : : : ; 4; 1; 1; : : : ; 1):

Thus, W ∪ W 0 is a resolving set of cardinality 2n for G. Since G contains H = K1; 2n+1

as an induced subgraph, it follows that
dim(G) 2n
6 :
dim(H ) 2n+1 − 1
Also, because
2n
lim =0
n→∞ 2n+1 − 1
 G. Chartrand et al. / Discrete Applied Mathematics 105 (2000) 99–113 113

there exists a graph G and an induced subgraph H of G such that dim(G)=dim(H ) is

arbitrarily small. We summarize this below.

Theorem 8. For every  ¿ 0; there exists a connected graph G and a connected

induced subgraph H of G such that dim(G)=dim(H ) ¡ .

References

[1] M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness,
Freeman, New York, 1979.
[2] F. Harary, R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191–195.
[3] C. Poisson, P. Zhang, The dimension of unicyclic graphs, J. Combin. Math. Combin. Comput., accepted.
[4] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549–559.
[5] P.J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci. 22 (1988) 445–455.