Total Resolving Sets in Graphs

P. Jeya Bala Chitra and S. Arumugam

National Centre for Advanced Research in Discrete Mathematics (n-CARDMATH)
Kalasalingam University
Anand Nagar, Krishnankoil-626126, INDIA.
e-mail: [email protected]

Abstract
Let G be a connected graph. Let W = (w1 , w2 , ..., wk ) be a subset of
V with an order imposed on it. For any v ∈ V , the vector r(v|W ) =
(d(v, w1 ), d(v, w2 ), ..., d(v, wk )) is called the resolving vector of v with respect
to W . If distinct vertices in V have distinct resolving vectors, then W is called
a resolving set of G. The minimum cardinality of a resolving set of G is called
the metric dimension of G and it is denoted by dim(G). A resolving set W is
called a total resolving set if the induced subgraph hW i has no isolated ver-
tices. The minimum cardinality of a total resolving set of G is called the total
resolving number of G and is denoted by tr(G). In this paper, we initiate a
study of this parameter.
Keywords : Resolving set, metric dimension, total resolving set, total resolving
number.

1 Introduction
The distance d(u, v) between two vertices u and v in a connected graph G is the
length of a shortest u-v path in G. For an ordered set W = {w1 , w2 , ..., wk } ⊂ V (G)
and a vertex v of G, we refer to the k-vector 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 any two distinct vertices have distinct representations with respect to
W . A resolving set for G containing a minimum number of vertices is a minimum
resolving set or a basis for G. The metric dimension dim(G) is the number of
vertices in a basis for G.
In [10] and later in [11], Slater introduced these ideas and he used the terms
locating set and location number for resolving set and metric dimension respectively.
Harary and Melter [5] discovered these concepts independently but used the term
metric dimension rather than location number.
Applications of resolving set arise in various areas including coin weighing prob-
lem [9], drug discovery [2], robot navigation [7], network discovery and verification
[1], connected joins in graphs [9], and strategies for mastermind game [4]. For a
survey of results in metric dimension we refer to Chartrand and Zhang [3].
The concept of domination is one of the major research areas in graph theory.
Several models of domination have been investigated by imposing conditions on
the subgraph induced by a dominating set. Some of the well studied parameters of
this type include connected domination, total domination, independent domination,
paired domination, global domination, weak domination, strong domination and
locating domination. In fact, more than 65 models of domination have been reported
in the appendix given in Haynes et al. [6]. Along the similar line Zhang and
Saenpholphat introduced the concept of connected resolving set [8].

1
 A resolving set W of G is connected if the subgraph hW i induced by W is
a nontrivial connected subgraph of G. The minimum cardinality of a connected
resolving set W of G is the connected resolving number cr(G). A connected resolving
set of cardinality cr(G) is called a cr-set of G. Since every connected resolving set
is a resolving set, dim(G) ≤ cr(G) for all connected graphs G. In this paper we
introduce the concept of total resolving set and total resolving number and present
several basic results.
We need the following definition and theorems:

Definition 1.1. Let G1 and G2 be two graphs of order n1 and n2 respectively. Then
the graph obtained by taking one copy of G1 and n1 copies of G2 and joining the
ith vertex of G1 to all the vertices in the ith copy of G2 is called the corona of G1
and G2 and is denoted by G1 ◦ G2 .

Definition 1.2. [7] Let T = (V, E) be a tree which is not a path and let v ∈ V. A
component S of T − {v} such that induced subgraph hS ∪ {v}i is a path is called a
leg at v.

Theorem 1.3. [7] Let T = (V, E) be Pa tree which is not a path. Let lv denote the
number of legs at v. Then dim(T ) = (lv − 1).
lv >1

Theorem 1.4. [8] Let G be a connected graph of order n ≥ 3. Then cr(G) = n − 1

if and only if G = Kn or K1,n−1 .

2 Total Resolving Sets

Definition 2.1. A resolving set W of a graph G is said to be a total resolving set if
the subgraph hW i induced by W has no isolated vertices. The minimum cardinality
of a total resolving set in a graph G is the total resolving number tr(G). A total
resolving set of cardinality tr(G) is called a tr-set of G.

Example 2.2. For the grpah G given in Figure 1, W = {v1 , v3 , v5 } is a basis for G
and W ′ = {v1 , v3 , v5 , v} is a minimum total resolving set. Hence dim(G) = 3 and
tr(G) = 4.

v1 v2
b b

v6 b b
v3

v
v5 b
b v4
Figure 1: A graph G with dim(G) = 3 and tr(G) = 4

Observation 2.3. If G is a connected graph of order n ≥ 3, then 2 ≤ tr(G) ≤ n−1.

The bounds are sharp. For the path Pn , n ≥ 3, we have tr(Pn ) = 2. For the complete
graph Kn , we have tr(Kn ) = n−1. Also tr(K1,n−1 ) = n−1. Since every non trivial
connected graph has no isolated vertices, tr(G) ≤ cr(G). Also tr(Pn ) = cr(Pn ) = 2
for all n ≥ 3. Hence the following problems arise naturally.

Problem 2.4. Characterize graphs for which tr(G) = 2.

2
Problem 2.5. Characterize graphs for which tr(G) = cr(G).
The total resolving number of standard graphs are given below.
Example 2.6.
(i) For the path Pn , n ≥ 2, tr(Pn ) = 2.
(ii) For the complete graph Kn , n ≥ 3, tr(Kn ) = n − 1.
(iii) For the complete bipartite graph Km,n , m, n ≥ 2, tr(Km,n ) = m + n − 2.
(iv) For the friendship graph G with k-triangles, k ≥ 2, tr(G) = k + 1.
(v) For the graph Pn + K1 , n ≥ 2, tr(Pn + K1 ) = ⌊n/2⌋.
Theorem 2.7. Let T be a tree which is not a path. Let s denote the number of
vertices v of T with lv > 1. Then tr(T ) = dim(T ) + s.
P
Proof. By Theorem 1.3, dim(T ) = (lv − 1). A basis W for T can be obtained
lv >1
by choosing one vertex from each of the lv − 1 legs at v which is adjacent to v, for
each v with lv > 1. Now, W1 = W ∪ {v ∈ V (T ) : lv > 1} is a total resolving set of
G. Hence tr(T ) ≤ dim(T ) + s. Now, let X be any total resolving set of T . Then
X contains at least one vertex from all but one leg for each v with lv > 1. Since
X is a total resolving set, X contains at least one more vertex from the subtree
induced by v and all the legs at v. Hence it follows that |X| ≥ dim(T ) + s, so that
tr(T ) ≥ dim(T ) + s. Thus tr(T ) = dim(T ) + s.
Theorem 2.8. Let G be a connected graph of order n ≥ 3. Then tr(G) = n − 1 if
and only if G = Kn or G = K1,n−1 .
Proof. Suppose tr(G) = n − 1. Since tr(G) ≤ cr(G), it follows that cr(G) = n − 1.
Hence it follows from by Theorem 1.4 that G = Kn or K1,n−1 . The converse is
obvious.
Theorem 2.9. Let G = K2n − M where M is a perfect matching in K2n . Then
tr(G) = n for all n ≥ 2.
Proof. Let V (K2n ) = {x1 , x2 , ..., x2n } and let M = {x1 x2 , x3 x4 , . . . , x2n−1 x2n }. Let
W = {x1 , x3 , ..., x2n−1 }. Since hW i is complete, hW i has no isolated vertices. Also
W is a resolving set of G and so tr(G) ≤ n. Now, suppose there exists a total
resolving set of G with |S| ≤ n − 1. Then there exists an edge in M such that its
end vertices are not in S and both these end vertices have the same representation
(1, 1, ..., 1), which is a contradiction. Thus tr(G) ≥ n and hence tr(G) = n.
Theorem 2.10. For the graph G = Kn − e, we have tr(G) = n − 2 for all n ≥ 3.
Proof. Let V (Kn ) = {x1 , x2 , ..., xn } and let e = x1 x2 . Then W = V − {x1 , x3 } =
{x2 , x4 , x5 , ..., xn } is a total resolving set of G and hence tr(G) ≤ n − 2. Also
any set W with |W | ≤ n − 3 is not a resolving set of G and hence it follows that
tr(G) ≥ n − 2. Thus tr(G) = n − 2.
Theorem 2.11. For any graph G, tr(G) ≤ 2 dim(G).
Proof. Let S be a resolving set of G with |S| = dim(G). For each v ∈ S, choose
v ′ ∈ V such that v ′ is adjacent to v. Then S1 = S ∪ {v ′ : v ∈ S} is a total resolving
set of G and tr(G) ≤ |S1 | ≤ 2dim(G).
The bound given in the above theorem is sharp as shown in the following theo-
rems:

3
Theorem 2.12. For the corona G ◦ K2 where G is any connected graph of order
n, we have dim(G) = n and tr(G) = 2n.

Proof. Let H = G ◦ K2 . Let V (G) = {v1 , v2 , . . . , vn } and V (H) = V (G) ∪

{w1 , w2 , . . . , wn }∪{w1′ , w2′ , . . . , wn′ }. Let E(H) = E(G)∪{wi vi : 1 ≤ i ≤ n}∪{wi′ vi :
1 ≤ i ≤ n}. Now, W = {wi : 1 ≤ i ≤ n} is a resolving set of H and S = W ∪ V (G)
is a total resolving set for H. Hence dim(H) ≤ n and tr(H) ≤ 2n. Also, any
resolving set of H must contain at least one vertex from {wi , wi′ } for each i and any
total resolving set must contain at least one vertex from {wi , wi′ } along with the
vertex vi for each i. Thus dim(H) ≥ n and tr(H) ≥ 2n. Hence dim(H) = n and
tr(H) = 2n.

Theorem 2.13. For the grid G = Pn Pn , n ≥ 2, we have tr(G) = 4.

Proof. Let G = Pn Pn and V (G) = {(ui , vj ) : 1 ≤ i, j ≤ n} where (u1 , u2 , ..., un )

and (v1 , v2 , ..., vn ) are the two paths of order n. Then W = {(u1 , v1 ), (u1 , v2 ),
(u1 , vn−1 ), (u1 , vn )} is a total resolving set of G and so tr(G) ≤ 4. Now, let
S ⊂ V (G) where |S| = 3 and hSi has no isolated vertices. Hence hSi is isomorphic
to P3 . Hence S is of one of the following forms:
S1 = {(ui , vj ), (ui , vj+1 ), (ui , vj+2 )} where j + 2 ≤ n and i ≥ 1.
S2 = {(ui , vj ), (ui , vj+1 ), (ui , vj+2 )} where j + 2 = n.
S3 = {(ui , vj ), (ui , vj+1 ), (ui , vj+2 )} where i = 1.
S4 = {(ui , vj ), (ui , vj+1 ), (ui+1 , vj+1 )} where j + 1 ≤ n and i ≥ 1.
S5 = {(ui , vj ), (ui , vj+1 ), (ui+1 , vj+1 )} where j + 1 = n.
If S = S1 , then (ui , vj+3 ) and (ui−1 , vj+2 ) have the same representation (3, 2, 1).
If S = S2 , then (ui , vj−1 ) and (ui+1 , vj ) have the same representation (1, 2, 3). If
S = S3 , then (ui , vj+3 ) and (ui+1 , vj+2 ) have the same representation (3, 2, 1). If
S = S4 , then (ui+1 , vj+2 ) and (ui+2 , vj+1 ) have the same representation (3, 2, 1). If
S = S5 , then (ui−1 , vj ) and (ui , vj−1 ) have the same representation (1, 2, 3). Hence
it follows that tr(G) ≥ 4. Thus tr(G) = 4.
Theorem 2.14. Let G be any connected graph of order n. If tr(G) = 2dim(G),
then every basis S of G is independent and no two vertices in S have a common
neighbour in G.

Proof. Let tr(G) = 2dim(G). Suppose there exists a basis S such that S is not
independent. For every isolated vertex v in hSi, we choose v ′ ∈ V \ S such that v ′
is adjacent to v. Let T = S ∪ {v ′ : v is an isolated vertex in S}. Then T is a total
resolving set of G and tr(G) ≤ |T | < dim(G), which is a contradiction. Hence every
basis S of G is independent. Now, suppose the vertices s1 , s2 ∈ S have a common
neighbour in G, say w. For every vertex v ∈ S − {s1 , s2 } we choose v ′ ∈ V \ S such
that v ′ is adjacent to v. Let T = S ∪ {v ′ : v ∈ S − {s1 , s2 }} ∪ {w}. Clearly, T is a
total resolving set of G and |T | ≤ 2 |S| − 1 which is contradiction. Thus every basis
S of G is independent and no two vertices in S have a common neighbour in G.

In this connection we propose the following conjecture:

Conjecture 2.15. For any graph G, tr(G) = 2dim(G) if and only if every basis S
of G is independent and no two vertices in S have a common neighbour in G.

Theorem 2.16. For any two positive integers k and n with 2 ≤ k ≤ n − 1, there
is a connected graph G of order n with total resolving number k.

Proof. For k = 2, the path Pn has the desired property. For k ≥ 3, let G be
the graph obtained from the path Pn−k+1 = (u1 , u2 , ..., un−k+1 ) by adding k − 1
pendant vertices vi , 1 ≤ i ≤ k − 1 adjacent to u1 . Then the order of G is n. Any
total resolving set of G must contain all the vertices vi , 1 ≤ i ≤ k − 1 and the vertex

4
u1 . Hence tr(G) ≥ k. Further W = {v1 , v2 , ..., vk−1 , u1 } is a total resolving set of
G. Thus tr(G) ≤ k and hence tr(G) = k.

In the following two theorems we present results on the total resolving number
of Cartesian product of graphs.

Theorem 2.17. If Cn is a cycle of order n ≥ 4, then tr(Cn K2 ) = 3.

Proof. Let G = Cn K2 and V (G) = {(ui , vj ) : 1 ≤ i ≤ n, j = 1, 2} where ((u1 , v1 ),

(u2 , v1 ), . . . , (un , v1 ), (u1 , v1 )) and ((u1 , v2 ), (u2 , v2 ), . . . , (un , v2 ), (u1 , v2 )) are the two
copies of Cn in G. Then W = {(u1 , v1 ), (u1 , v2 ), (u2 , v1 )} is a total resolving set of
G and so tr(G) ≤ 3. Now, let S ⊂ V (G) where |S| = 2 and hSi has no isolated ver-
tices. Then hSi is isomorphic to K2 and S is of the form S1 = {(ui , vj ), (ui+1 , vj )}
or S2 = {(ui , vj ), (ui , vj+1 )} where the addition in the suffix is taken modulo n. If
S = S1 , then (ui−1 , vj ) and (ui , vj+1 ) have the same representation. If S = S2 ,
then (ui−1 , vj ) and (ui+1 , vj ) have the same representation. Hence it follows that
tr(G) ≥ 3. Thus tr(G) = 3.

Theorem 2.18. For a non trivial connected graph G, tr(GK2 ) ≤ tr(G) + 1.

Proof. Let H = GK2 . Let G1 and G2 be two copies of G in H. Let V (H) =

V (G1 ) ∪ V (G2 ) and E(H) = E(G1 ) ∪ E(G2 ) ∪ {ui vi : ui ∈ V (G1 ), vi ∈ V (G2 )}.
Suppose that W = {w1 , w2 , ..., wk } is a total resolving set of G. Let W1 =
{x1 , x2 , ..., xk } and W2 = {y1 , y2 , ..., yk } be the corresponding total resolving sets in
G1 and G2 respectively. Let W ′ = W1 ∪ {y1 }. We claim that W ′ is total resolving
set of GK2 , which implies that tr(GK2 ) ≤ tr(G) + 1. Since hW1 i is subgraph
of G having no isolated vertices and y1 is adjacent to x1 , it follows that hW ′ i is a
subgraph of GK2 having no isolated vertices. It remains to show that W ′ is a re-
solving set of GK2 . If u ∈ V (G1 ), then dGK2 (u, xi ) = dG1 (u, xi )(1 ≤ i ≤ k) and
dGK2 (u, y1 ) = dG1 (u, x1 ) + 1. If u ∈ V (G2 ), then dGK2 (u, xi ) = dG1 (v, xi ) + 1
where v ∈ V (G1 ) corresponds to u and dGK2 (u, y1 ) = dG1 (v, x1 ). Thus if u ∈
V (G1 ), then r(u|W ′ ) = (dG1 (u, x1 ), dG1 (u, x2 ), ..., dG1 (u, xk ), dG1 (u, x1 ) + 1). If u ∈
V (G2 ), then r(u|W ′ ) = (dG1 (v, x1 ) + 1, dG1 (v, x2 ) + 1, ..., dG1 (v, xk ) + 1, dG1 (v, x1 ))
where v ∈ V (G1 ) corresponds to u. Since W1 is a resolving set of G1 , the rep-
resentations r(u|W ′ ) are distinct and so W ′ is a resolving set of GK2 . Thus
tr(GK2 ) ≤ tr(G) + 1.

We observe that if n is any integer with n ≥ 2 and G = Kn or Pn , then

tr(GK2 ) = tr(G). Also , if n ≥ 4, then tr(Cn K2 ) = tr(Cn ) + 1. Hence the
following problem naturally arises.

Problem 2.19. Characterize graphs for which tr(GK2 ) = tr(G) + 1.

3 Conclusion and Scope

Motivated by the concept of connected resolving sets introduced in [8], in this paper
we have initiated a study of total resolving sets. We have presented several basic
results and problems for further investigation. Other types of conditional resolving
sets such as independent resolving set, paired resolving set and global resolving
set are interesting topics for further research and results in this direction will be
reported in subsequent papers.

5
References
[1] Z. Beuliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffman, M. Mihalak and
L. Ram, Network Discovery and Verification, IEEE J. Sel. Areas commun., 24
(2006), 2168–2181.

[2] V. Chavatal, Mastermind, combinatorica, 3 (1983), 325–329.

[3] G. Chartrand, L. Eroh, M. Johnson and O.R. Oellermann, Resolvability in

graphs and the metric dimension of a graph, Discrete Appl. Math., 105 (2000),
99–113.
[4] G. Chartrand and P. Zhang, The theory and application of resolvability in
graphs: A survey, Congr. Numer., 160 (2003), 47–68.

[5] F. Harary and R.A. Melter, On the metric dimension of a graph, Ars. Combin.,
2 (1976), 191–195.

[6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination
in graphs, Marcel Dekker Inc., Newyork, (1998).

[7] S. Khuller, B. Raghavachari and A. Rosenfield, Landmarks in graphs, Discrete

Appl. Math., 70 (1996), 217–229.

[8] V. Saenpholphat and P. Zhang, Connected Resolvability of graphs, Czechoslo-

vak Mathematical Journal, 53 (2003), 827–840.

[9] A. Sebo and E. Tannier, On metric generators of graphs, Math. Oper. Res, 29
(2004), 383–393.

[10] P.J. Slater, Leaves of Trees, Congr. Numer., 14 (1975), 549–559.

[11] P.J. Slater, Dominating and reference sets in graphs, J. Math. Phys. Sci., 22
(1988), 445–455.