## Weak total resolving sets in graphs

I. Javaid , M. Salman , M. Murtaza , F. Iftikhar 1 ∗ 1 1 1 and M. Imran 2

1 Center for Advanced Studies in Pure and Applied Mathematics, Bahauddin Zakariya University Multan, 60800, Pakistan

Email: ijavaidbzu, solo33, mahru830, farheen689 @gmail.com 2 School of Natural Sciences, National University of Science and Technology,

{ } Islamabad, Pakistan, Email: imrandhab@gmail.com

## Abstract

A set W of vertices of G is said to be a weak total resolving set for G if W is a resolving set for G as well as for each w ∈ W , there is at least one element in W -{ w } that resolves w and v for every v ∈ V ( G ) -W . Weak total metric dimension of G is the smallest order of a weak total resolving set for G . This paper includes the investigation of weak total metric dimension of trees. Also, weak total resolving number of a graph as well as randomly weak total k -dimensional graphs are defined and studied in this paper. Moreover, some characterizations and realizations regarding weak total resolving number and weak total metric dimension are given.

Keywords: Metric dimension; weak total metric dimension; weak total resolving number; randomly weak total k -dimensional graph; twins AMS Subject Classification Numbers: 05C12

## 1 Introduction

/negationslash

Unless otherwise specified, all the graphs G considered in this paper are simple, non-trivial and connected with vertex set V ( G ) and edge set E G ( ). Two adjacent vertices u, v in G will be denoted by u ∼ v , and non-adjacent vertices u , v will be denoted by u ∼ v . The subgraph induced by a set S of vertices of G is denoted by 〈 S 〉 . Two isomorphic graphs G and H are denoted by G ∼ = H . The neighborhood of a vertex v of G is the set N v ( ) = { u ∈ V ( G ) | u ∼ v } . The number of elements in N v ( ) is the degree of v , denoted by d v ( ). The maximum degree of G is denoted by ∆( G ). If two distinct vertices u and v of G have the property that N u ( ) -{ } v = N v ( ) -{ } u , then u and v are called twin vertices (or simply twins) in G . If for a vertex u of G , there exists a vertex v = u in G such that u, v are twins in G , then u is said to be a twin in G . If 〈 N v ( ) 〉 ∼ = K d v ( ) for v ∈ V ( G ), then v is called a complete vertex in G . The number d u, v ( ) denotes the distance between two

/negationslash

∗ Corresponding author email: ijavaidbzu@gmail.com

vertices u and v of G , which is the number of edges in a shortest u -v path in G . The maximum distance between two vertices in G is called the diameter of G , denoted by diam G ( ). Two vertices u, v of G are said to be antipodal if d u, v ( ) = diam G ( ) otherwise, u and v are called non-antipodal . A vertex of degree one is called a leaf in G . A vertex of degree at least three in G is called a major vertex . An end vertex u is a terminal vertex of a major vertex v such that d u, v ( ) &lt; d u, w ( ) for each other major vertex w . The number of terminal vertices for a major vertex v is its terminal degree td v ( ). If td v ( ) &gt; 0 for a major vertex v , then v is called an exterior major vertex . The sum ∑ td v ( ) taken over all the major vertices v of G is denoted by σ G ( ), and ex G ( ) denotes the number of exterior major vertices of G . The symbol X /triangleinv Y denotes the symmetric difference of two sets X and Y .

/negationslash

/negationslash

A vertex x of G resolves (or distinguishes ) two distinct vertices y, z of G if d y, x ( ) = d z, x ( ). The k -tuple c U ( v ) = ( ( d v, u 1 ) , d ( v, u 2 ) , . . . , d ( v, u k )) is the code of v with respect to a set U = { u , u 1 2 , . . . , u k } ⊆ V ( G ). A subset W of V ( G ) is called a resolving set for a graph G if for every two distinct vertices u and v of G , there is an element w in W that resolves u and v . Equivalently, the set W is a resolving set if for every two vertices u and v of G , we have c W ( u ) = c W ( v ). The minimum cardinality of a resolving set for G is called the metric dimension of G , denoted by dim( G ). A resolving set of cardinality dim( G ) is called a metric basis of G . This concept was firstly studied by Slater in 1975 in [14] with the names locating set and location number rather than resolving set and metric dimension. The terminologies, we used above for this concept and will be used throughout this paper, was proposed by Harary and Melter when they independently studied this concept in 1976 [8]. This concept has wide range of applications not just in graph theory but to many other fields. For instance, Khuller et al. studied its application in robot navigation [12]; Melter and Tomescu studied its application in pattern recognition and image processing [13], to name a few. First time, in 1979, Gary and Johnson noted that to determine the metric dimension of a graph is an NP-hard problem [7], however, its explicit construction was given by Khuller et al. in 1996 [11].

/negationslash

/negationslash

Elements of a metric basis were referred to as sensors in many applications. If one of the sensors, say s , placed at a location stops working due to any impenetrable difficulty, then we will not receive enough information regarding the detection of those two locations where no sensor is placed and they are only be detected by the sensor s . This kind of problem was solved by defining fault-tolerant resolving set, which was defined by Hernando et al. in 2008 [9] in the following way: a resolving set W for a graph G is fault-tolerant if W \ { v } is also resolving set for each v in W . But, a problem still to be addressed is: let the two locations, say L 1 , L 2 , on which L 1 is where the sensor s placed and L 2 is where no sensor placed, and let they are only be detected by the sensor s . Then which of the other placed sensors provides the complete information regarding the detection of the locations L 1 and L 2 if the sensor s stops working? The answer of this kind of problems leads to introduce the concept of total resolving set. This concept was introduced by Javaid et al. in 2012 [10] in the following way: a resolving set for a graph G is called a total resolving set, written as TR-set, if for every pair of distinct vertices u, v in G , there is a vertex w in W such that d u, w ( ) = d v, w ( ) for u, v = w (it was named strong total resolving set in [10], but in analogy with total dominations in graphs in [6], we use the term total resolving sets). But complete graphs or graphs with twin vertices do not have any total resolving sets. On relaxing a condition in total resolving set, a new parameter, named as weak total resolving set, defined

/negationslash by Javaid et al. in [10] as: a resolving set W for a graph G is called a weak total resolving set , simply written as WTR-set, if for every pair of distinct vertices u, v of G with u ∈ V ( G ) -W and v ∈ W , there is a vertex w ∈ W -{ } v such that d u, w ( ) = d v, w ( ). Here, in this paper, we extend the study of this concept and define and study some new parameters in the context of weak total resolvability. One thing important to note here is that one might think that the two concepts: the concept of fault-tolerant resolving set and the concept of weak total resolving set, are equivalent. But, a comparison between these two concepts, given in [10], shows that they are not equivalent.

The cardinality of a minimum WTR-set is called the weak total metric dimension (WTMD) of G , denoted by dim wt ( G ). A WTR-set of cardinality dim wt ( G ) is called a weak total metric basis (WTMB) of G . The weak total resolving number of a graph G , denoted by res wt ( G ), is the minimum positive integer r such that every r -set of vertices of G is a WTR-set for G . Chartrand and Zhang in [4] considered graphs G with dim( G ) = res G ( ). They called these graphs randomly k -dimensional graphs, where k = dim( G ). We say that a graph G is randomly weak total k -dimensional if dim wt ( G ) = res wt ( G ) = k . The aim of this paper is to study the three parameters dim wt ( G ), res wt ( G ) and randomly weak total k -dimensional graph. We investigate dim wt ( G ) and res wt ( G ) when G is a tree. Also, we reveal some properties of graphs G having dim wt ( G ) = 2 and characterize all the graphs G with dim wt ( G ) = | G | . Moreover, we classify the graphs G with res wt ( G ) = 3 and res wt ( G ) = | G | .

## 2 Weak total metric dimension

The following useful result for finding the weak total metric dimension of graphs was proposed in [10].

Lemma 1. [10] A resolving set W for a graph G is a WTR -set if and only if the code, with respect to W , of each x ∈ V ( G ) -W differ by at least two coordinates from the code, with respect to W , of each w ∈ W .

/negationslash

Let u, v be two twins in a graph G and let W be a WTR-set for G such that u ∈ W and v ∈ W . Since d u, w ( ) = d v, w ( ) for all w ∈ V ( G ) -{ u, v } , so the codes of u and v , with respect to W , differ by one coordinate only. Thus, Lemma 1 concludes the following remark:

Remark 2. Every WTR-set for a graph G contains all the twins of G .

Since every WTR-set for a graph G is a resolving set as well, so the following is trivial relationship between dim( G ) and dim wt ( G )

$$\dim ( G ) \leq \dim _ { w t } ( G ).$$

To see the equality holds in (1), construct a graph as follows: Take two copies of K 3 with vertex sets { u, v, w } and { x, y, z } . Take a path P a ≥ 2 with its two leaves called l 1 , l 2 . By an edge attach one leaf l with u and one leaf l ′ with x . Identify the leaf l 1 with the vertex v and the leaf l 2 with the vertex y . Call the resultant graph G . Since G is not a path and no single vertex forms a WTR-set for G , so dim( G ) ≥ 2 and dim wt ( G ) ≥ 2. Further, the set { l, l ′ } is a resolving set as well as WTR-set for G and, as a consequence, dim( G ) = dim wt ( G ) = 2. To see the inequality

/negationslash holds in (1), let the graph G = K r + ( K 1 ∪ K s ) of order n = r + s + 1 for r, s ≥ 2 ( G + H is the join (sum) of the graph G and H ). It was investigated in [5] that dim( G ) = n -2. We claim that dim wt ( G ) = n -1 or n . But, dim wt ( G ) = n because the set V ( G ) -V ( K 1 ) is a WTR-set for G . Since each element of the sets V ( K r ) and V ( K s ) is twin in G , Remark 2 concludes that dim wt ( G ) ≥ r + s = n -1, and, as a consequence, dim( G &lt; ) dim wt ( G ) = n -1.

Due to the relationship (1), we have the following assertions:

Proposition 3. If m is the weak total metric dimension of a graph G and D = diam G ( ) , then the following assertions hold:

- (1) The maximum order of G is D m + m .
- (2) the maximum degree of G is at most 3 m -1 .
- (3) G is at most 2 m -colorable.

Proof. Let k denotes the metric dimension of G . Then D,k and m all are positive integers.

Khuller et al. proved in [11] that | G | ≤ D k + k . Thus, the inequality (1) implies part (1) of the theorem.

Chartand et al. proved in [2] that k ≥ log (∆( 3 G ) + 1) ( i.e , ∆( G ) ≤ 3 k -1). Therefore, the inequality (1) follows the part (2) of the theorem.

Let χ G ( ) denotes the minimum number of colors needed to color the graph G properly ( i.e , chromatic number of G ). It was shown by Chappell et al. in [1] that χ G ( ) ≤ 2 k and, as a result, G is at most 2 m -colorable, by the inequality (1).

## 3 Graphs G with dim wt ( G ) = 2 and dim wt ( G ) = n

The following result proved by Khuller et al. in [11] is useful.

Proposition 4. [11] Let G be a graph and u, v, w be three vertices of G such that u ∼ v . If d v, w ( ) = d , then d u, w ( ) ∈ { d -1 , d, d +1 } .

Now, we explore some properties of graphs with dim wt ( G ) = 2 in the next few results.

/negationslash

Proposition 5. Let G be a graph of order at least three. If { u, v } be a WTMB of G , then u ∼ v .

Proof. If u ∼ v , then the codes (with respect to the set { u, v } ) of u and the other neighbor of v differ by one coordinate only, and hence { u, v } is not a WTR-set for G , by Lemma 1.

Corollary 6. If dim wt ( G ) = 2 and { u, v } be a WTMB of G , then u ∼ v if and only if G is isomorphic to K 2 .

Proposition 7. Let G be a graph of order at least four. If dim wt ( G ) = 2 and { u, v } be a WTMB of G , then u and v are not twins in G . In fact, G has no twin.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0649v1-figure-3b233765-446d-485a-adda-1bdcf16a0e4e.jpg)

Proof. Suppose that u and v are twins in G . If u ∼ w and v ∼ w for all w ∈ V ( G ) -{ u, v } , then { u, v } is not a resolving set for G . If { u, v } is a resolving set for G , then the code (with respect to the set { u, v } ) of a neighbor of a common neighbor of u and v differ by one coordinate only from the codes of u and v , a contradiction by Lemma 1.

Corollary 8. If dim wt ( G ) = 2 , then G has twins if and only if G is isomorphic to P 2 or P 3 .

Theorem 9. If dim wt ( G ) = 2 and { u, v } be a WTMB of G , then degree of u and v is at most two.

Proof. Let d u, v ( ) = p , then p ≥ 2 by Proposition 5. Proposition 4 yields that the second (first) coordinate of the code, with respect to the set { u, v } , of a neighbor of u (or v ) is one of { p -1 , p, p +1 . But, (1 } , p ) (or ( p, 1)) cannot be the code of any neighbor of u (or v ), by Lemma 1. Since { u, v } is a resolving set so both u and v can have at most two neighbors.

Theorem 10. If dim wt ( G ) = 2 and { u, v } be a WTMB of G , then the followings are true:

- (1) The geodesic P between u and v is unique.
- (2) Each neighbor of u and v has degree at most three.
- (3) Every vertex on P , other than u, v and their neighbors, has degree at most five.
- (4) The maximum degree of G is at most eight.

/negationslash

- (5) For any w ∈ { u, v } and for each z ∈ N w ( ) , r ∼ w for all r ∈ N z ( ) .

Proof. (1) Suppose there are two geodesics P and Q between u and v . Then, clearly, there are two vertices x, y on P, Q , respectively, such that u is equidistant from x and y and, as a result, c { u,v } ( x ) = c { u,v } ( y ), a contradiction to the fact that { u, v } is a resolving set for G .

/negationslash

- (2) Let x be a neighbor of u and d x, v ( ) = t , then d u, v ( ) ∈ { t -1 , t, t + 1 } by Proposition 4. But, d u, v ( ) = t , for otherwise, u and v do not form WTR-set for G , by Lemma 1. Thus d u, v ( ) = t -1 or t + 1. Assume, without any distress, that d u, v ( ) = t -1. Then out of three possibilities for the second coordinate of the codes of other neighbors of x , only two possibilities are left. It follows that x can have at most two more neighbors (as its one neighbor is u ) since { u, v } is a WTR-set for G .

/negationslash

- (3) Let y be a vertex on the unique geodesic P between u and v such that y ∈ { u, v }∪ N u ( ) ∪ N v ( ). Let ( a, b ) be the code of y , then d u, v ( ) = a + . The possible codes for the neighbors of b y are: ( a -1 , b -1) , ( a -1 , b ) , ( a -1 , b +1) ( , a, b -1) , ( a, b ) , ( a, b +1) ( , a +1 , b -1) , ( a +1 , b ) , ( a +1 , b +1). Out of these nine pairs, the pairs ( a -1 , b -1) , ( a -1 , b ) , ( a, b ) , ( a, b -1) cannot be the code of any neighbor of y . Otherwise, either the geodesic between u and v is not unique or { u, v } is not a resolving set for G . It follows that d y ( ) ≤ 5.
- (4) Since dim wt ( G ) = 2, so the result follows by Proposition 3.
- (5) By part (2), let N z ( ) = { u, i, j } for any z ∈ N u ( ). Since the graphs considered in this paper are simple, we claim that neither i ∼ u nor j ∼ u . Let d z, v ( ) = q , then the possible second coordinate of the code of u is one of { q -1 , q +1 . Without loss of generality, assume that } q -1 is the second coordinate of the code of u , q is the second coordinate of the code of i and q +1 is the second coordinate of the code of j . Now, if i ∼ u , then c { u,v } ( z ) = c { u,v } ( ), and if i j ∼ u , then d j, v ( ) would be q rather than q +1 and hence c { u,v } ( z ) = c { u,v } ( j ).

Theorem 11. If dim wt ( G ) = 2 , then G cannot have a complete vertex of degree more than three.

Proof. Assume that G has a complete vertex of degree more than three. The G has a complete graph of order ≥ 5 as a subgraph. But, since a WTR-set for G of cardinality two is also a resolving set for G and Khuller et al. in [11] proved that any graph having a resolving set of cardinality two cannot have K 5 as a subgraph. It completes the proof.

Since a graph having a resolving set of order two cannot have K 5 as a subgraph [11], so we have the following straightforward consequences:

Corollary 12. If dim ( G ) = 2 , then wt (1) G is at most 4-colorable,

- (2) the clique number of G is at most 4.

In the following result, we classify the graphs having weak total metric dimension equals to the order of the graphs.

Theorem 13. A graph G of order n ≥ 2 has dim wt ( G ) = n if and only if each vertex of G is twin.

/negationslash

Proof. For n = 2, the result is trivial so we consider n ≥ 3. Assume that each vertex of G is twin. Let u be any arbitrary vertex of G . Since u is twin, there is a vertex v = u in G such that d u, w ( ) = d v, w ( ) for all w ∈ V ( G ) -{ u, v } . It follows that V ( G ) -{ } u is not a WTR-set for G . Hence, dim wt ( G ) = n .

Now, assume that dim wt ( G ) = n . If we suppose that a vertex x is not twin in G , then the code of every element of the set V ( G ) -{ } x with respect to this set differ by at least two coordinates from the code of x with respect to V ( G ) -{ } x . It follows that the set V ( G ) -{ } x is a WTR-set for G , a contradiction.

## 4 Weak total resolving number and randomly weak total k -dimensional graphs

Now, we proceed to characterize the graphs where the bounds 3 ≤ res wt ( G ) ≤ n are achieved. First of all, we obtain the lower bound.

Proposition 14. For any graph G of order n ≥ 3 , res wt ( G ) ≥ 3 .

Proof. Let x, y ∈ V ( G ) be two vertices such that x ∼ y and let z ∈ V ( G ) - { x, y } be a vertex such that z ∼ y . Since d x, y ( ) = 1 = d y, z ( ), the set { x, y } is not a WTR-set for G and, as a consequence, res wt ( G ) ≥ 3.

Theorem 15. Let G be a graph of order n ≥ 3 . Then res wt ( G ) = n if and only if G contains a twin.

/negationslash

Proof. If G ∼ = K n or G ∼ = P 3 , then res wt ( G ) = n and we are done. So we assume that n ≥ 4 and G ∼ = K n .

/negationslash

/negationslash

Let u be a twin in G , then there exists a vertex v = u such that u and v are twin vertices of G . For any k ∈ { 3 , . . . , n - } 1 , there exists a k -set of vertices W such that u ∈ W and v ∈ W , and then for any w ∈ W -{ } u , d w, u ( ) = d w, v ( ). Hence, res wt ( G ) = n .

/negationslash

Now, we assume that G has no twin and let v ∈ V ( G ). In this case for any u ∈ V ( G ) -{ } v , there exists w ∈ N u ( ) /triangleinv N v ( ) - { u, v } . Since d w, u ( ) = d w, v ( ), we have that V ( G ) - { v } is a WTR-set and, as a consequence res wt ( G ) ≤ n -1.

From Theorem 13, we deduce the following consequence:

Corollary 16. A graph G of order n is a randomly weak total n -dimensional graph if and only if each vertex of G is twin.

Also, from Theorem 15 and Corollary 16, we conclude that a graph G of order n is a randomly weak total ( n -1)-dimensional graph if and only if dim wt ( G ) = n -1 and G has no twin.

In order to give a characterization of the graphs with res wt ( G ) = 3, we present the following lemma:

Lemma 17. If res wt ( G ) = k , then every two vertices of G have at most k -2 common neighbors.

Proof. We proceed by contradiction. Let res wt ( G ) = k and suppose that there exist u, v ∈ V ( G ) such that | N u ( ) ∩ N v ( ) | ≥ k -1. Let W be a set composed by u and k -1 elements of N u ( ) ∩ N v . ( ) Then for any w ∈ W - { u } , we have that d w, u ( ) = d w, v ( ), which is a contradiction because | W | = k and res wt ( G ) = k .

Theorem 18. Let G be a graph. Then res wt ( G ) = 3 if and only if G is a cycle graph of odd order or G is a path of order greater than or equal to three.

Proof. If G is an odd cycle or a path of order n ≥ 3, then any pair of vertices is a resolving set. Hence, any set composed by three vertices of G is a WTR-set and, by Proposition 14, we conclude that res wt ( G ) = 3.

/negationslash

On the other hand, if G ∼ = C n , where n is even, then for any pair of antipodal vertices x, y and the neighbors of x , say a and b , we have that d a, x ( ) = d b, x ( ) = 1 and d a, y ( ) = d b, y ( ) = n 2 -1, and then { x, y, a } is not a WTR-set for G . Thus, res wt ( G ) = 3.

It remains to show that if res wt ( G ) = 3, then ∆( G ) ≤ 2. Suppose that there exist four different vertices a, b, c, d ∈ V ( G ) such that b, c, d ∈ N a ( ). In such a case, we differentiate the following cases for the subgraph induced by the set { b, c, d } :

Case 1: 〈{ b, c, d }〉 ∼ = N 3 (an empty graph). Since d b, c ( ) = d b, d ( ) = 2 and d a, c ( ) = d a, d ( ) = 1, we conclude that { a, b, c } is not a WTR-set for G .

Case 2: 〈{ b, c, d }〉 ∼ = K 2 ∪ K 1 . We assume, without loss of generality, that c ∼ d . In this case, d b, c ( ) = d b, d ( ) = 2 and d a, c ( ) = d a, d ( ) = 1 and so we conclude that { a, b, c } is not a WTR-set for G .

/negationslash

/negationslash

Case 3: 〈{ b, c, d }〉 ∼ = P 3 . Now, we assume, without loss of generality, that c ∼ d . In this case, | N a ( ) ∩ N b ( ) | ≥ 2 and, by Lemma 17, we conclude that res wt ( G ) = 3.

/negationslash

Case 4: 〈{ b, c, d }〉 ∼ = K 3 . As above, | N a ( ) ∩ N b ( ) | ≥ 2 and, by Lemma 17, we conclude that res wt ( G ) = 3.

According to the above cases, we deduce that if res wt ( G ) = 3, then ∆( G ) ≤ 2. Therefore, the result follows.

It is easy to check that the two extremes of any path graph form a WTR-set. Also, it was shown in [10] that for any cycle graph dim wt ( C n ) = 3 . Therefore, Theorem 18 leads to the following corollary:

Corollary 19. A graph is randomly weak total 3 -dimensional if and only if it is a cycle graph of odd order.

The maximum degree of a graph according to its weak total resolving number is investigated in the next result.

Theorem 20. If res wt ( G ) = k , then maximum degree of G is at most 2 k -1 + k -1 .

Proof. Let u be a vertex of G with d u ( ) = ∆( G ) and let a set U = { u, u , u 1 2 , . . . , u k -1 } of order k , where u , u , . . . , u 1 2 k -1 ∈ N u ( ). Since res wt ( G ) = k , so U is a WTR-set for G . Indeed for x ∈ N u ( ) -U , d x, u ( ) = 1 and d x, u ( i ) = 1 or 2 (1 ≤ i ≤ k -1). It follows that the maximum number of distinct codes with respect to U for the elements of N u ( ) -U is 2 k -1 . Thus | N u ( ) -U | ≤ 2 k -1 and, as a consequence, ∆( G ) = d u ( ) ≤ 2 k -1 + k -1.

The next result gives the realization of weak total metric dimension and weak total resolving number of some connected graphs.

Theorem 21. For every two natural numbers a, b with 3 ≤ a ≤ b , there exists a graph G such that dim wt ( G ) = a and res wt ( G ) = b .

Proof. For a = . Let b G be a graph of order b in which each vertex is twin. Then dim wt ( G ) = a = b = res wt ( G ).

For a = 3 and b ≥ 4. Consider the complete graph K 3 with vertex set { s, t, u } and the path P b -a +1 with one leaf called l . Make the graph G of order b by identifying the leaf l of P b -a +1 with the vertex u of K 3 . Note that, G has two twins s, t and s ∼ t . Since only two adjacent vertices do not form WTR-set for G , by Propositions 5, so dim wt ( G ) ≥ 3. Clearly, the vertex set of K 3 is a WTR-set for G and, as a result, dim wt ( G ) = a . Moreover res wt ( G ) = b , by Theorem 15.

For 4 ≤ a = b -1. Take a vertex v and attach a leaves l 1 , l 2 , . . . , l a by an edge with v . The resultant graph G is a star graph and has order a + 1. Since all the leaves are twins and the collection of all these twins forms a WTR-set for G , so Remark 2 and Theorem 15 yield that dim wt ( G ) = a and res wt ( G ) = a +1.

For 4 ≤ a ≤ b -2. Consider the graph K 4 -e (obtained by deleting one edge e from K 4 ) with vertex set { w, x, y, z } and e = y ∼ z . Attach a -2 leaves l 1 , l 2 , . . . , l a -2 by an edge with the vertex w of K 4 -e . Also, identify a leaf l of the path P b - -a 1 with the vertex x of K 4 -e ( P 1 ∼ = K l with unique vertex l ). Call the resultant graph G . Clearly, order of G is b . Since y, z and all the leaves l 1 , l 2 , . . . , l a -2 are twins in G and the set { y, z, l 1 , l 2 , . . . , l a -2 } is a WTR-set for G , it follows that dim wt ( G ) = a and res wt ( G ) = b , by Remark 2 and Theorem 15.

## 5 Weak total metric dimension and weak total resolving number of a non-path tree

Let G be a non-path tree (we call a tree which is not a path, a non-path tree) and { v k : 1 ≤ k ≤ ex G ( ) } be the set of exterior major vertices of G . If two or more paths start from an exterior major vertex v k and end at different terminal vertices of v k , then they are called the branches rooted at v k . Let P k i : u k i, 1 = v , u k k i, 2 , ..., u k i,l k i (1 ≤ i ≤ t k ) be the t k ≥ 2 branches of v k where

l k i is the number of vertices in branch P k i and indices i, j, k in u k i,j represent that vertex is at j th position in i th branch P k i of k th exterior major vertex v k . In our later discussion, absence of index k in P k i , u k i,j and t k means that only one exterior major vertex v is under consideration. For our convenience, we label branches P k i in ascending order of i so that for any two branches P k r , P k s , r &lt; s if l k r ≤ l k s . If l k i = l k (1 ≤ i ≤ t k ) and t k ≥ 2, then branches P k i are called similar branches of v k each of length l k -1. If l k i = 2 (1 ≤ i ≤ t k ) and t k ≥ 2 for an exterior major vertex v k , then similar branches of v k are called twin leaves . Let P k i and P k s be two similar branches of an exterior major vertex v k , then vertex u k i,j in P k i is at same position as u k s,j in P k s . We name another branch which plays an important role in finding WTMB of a non-path tree. A branch P k 1 of an exterior major vertex v k is called the unique branch of shortest length if l k 1 &lt; l k i for all (2 ≤ i ≤ t k ). In fact, if an exterior major vertex has twin leaves, then it does not have the unique branch of shortest length.

Remark 22. Let G be a non-path tree and v be an exterior major vertex of G with t ≥ 2 branches P i (1 ≤ i ≤ t ) . If a set W ⊆ V ( G ) is a resolving set for G , then W contains at least one vertex other than v from at least t -1 branches of v . Let W ∩ { V ( P t -1 ) ∪ V ( P t ) } = ∅ , then the code of u t -1 1 , and u t, 1 with respect to W become same as these two vertices are at the same distance from vertices of W , a contradiction that W is a resolving set.

Proposition 23. Let v be an exterior major vertex of a graph G and let P r , P s be two branches of v with l r , l s number of vertices respectively and l r &lt; l s . If W is a WTR-set of G and W contains a vertex from P r other than v , then W must contains at least one vertex from P s other than v .

Proof. Suppose u r,j ∈ W ∩ V ( P r ) for some fix j ; 1 ≤ j ≤ l r and W ∩ V ( P s ) = ∅ . As d u ( s,j , w ) = d u ( r,j , w ) for all w ∈ W \ { u r,j } , therefore the code (with respect to W ) of the vertex u s,j ∈ P s lying at the jth position in P s , differ by one coordinate only from the code (with respect to W ) of u r,j ∈ W and, as a consequence, W is not a WTR-set for G , by Lemma 1.

Theorem 24. Let G be a non-path tree and W be a WTMB of G . Let v be an exterior major vertex of G with t branches { P i : 1 ≤ i ≤ } t in which P 1 is the unique branch of shortest length with l 1 number of vertices. Then W must contains vertices u i,j ∈ P i for each i (2 ≤ i ≤ t ) and exactly one j ( j &gt; l 1 ) .

/negationslash

Proof. Since W is a resolving set for G so by Remark 22, W contains at least one vertex from at least t -1 branches of v . We start by choosing W ∩ V ( P 1 ) = ∅ , i.e., W does not contain any vertex from P 1 , then W contains at least one vertex from each P i (2 ≤ i ≤ t ). If we take u i,j ∈ W ∩ V ( P i ) for some i (2 ≤ i ≤ t ) and some j where j ≤ l 1 , then d u ( 1 ,j , w ) = d u ( i,j , w ) for all w ∈ W \ { u i,j } , so the code of u 1 ,j ∈ P 1 and the code of u i,j ∈ W with respect to W , differ by one coordinate only, which is a contradiction that W is a WTMB of G . Thus for u i,j ∈ W ∩ V ( P i ), j must be greater than l 1 . Also W is a WTMB of G if | W ∩ V ( P i ) | is minimum which is possible only when we take exactly one vertex from each P i (2 ≤ i ≤ t ). Thus if W ∩ V ( P i ) = { u i,j ∈ P i : for each i (2 ≤ i ≤ t ) and exactly one j ; j &gt; l 1 } , then | W ∩ V ( P i ) | = t -1 which is minimum and the codes of vertices of P 1 differ by at least two coordinates from the codes of vertices of W with respect to W . Moreover if we choose W ∩ V ( P 1 ) = ∅ , then by Proposition 23, | W ∩{ V ( P i ) : (1 ≤ i ≤ t ) }| = t as l 1 &lt; l i for all (2 ≤ i ≤ t ). Thus | W ∩ V ( P i ) | is not minimum, which is contradiction that W is a WTMB of G .

Theorem 25. Let G be a non-path tree and W be a WTMB of G . Let v be an exterior major vertex of G with t branches { P i : 1 ≤ i ≤ } t and v does not have the unique branch of shortest length. Then W must contains vertices u i,j ∈ P i for each i (1 ≤ i ≤ t ) and exactly one j (2 ≤ j ≤ l i ) .

/negationslash

Proof. Since v does not have the unique branch of shortest length, so there exist s (2 ≤ s ≤ t ) similar branches { P i : 1 ≤ i ≤ s } of v , each has l = l i (1 ≤ i ≤ s ) number of vertices. Also { P i : s &lt; i ≤ } t are remaining t -s branches of v . As W is a resolving set of G so by Remark 22, W contains at least one vertex from at least t -1 branches of v . We start by choosing W ∩ V ( P 1 ) = ∅ , i.e., W does not contain any vertex from P 1 , then W contains at least one vertex from P i (2 ≤ i ≤ t ). If we choose u i,j ∈ W ∩ V ( P i ) for some i (2 ≤ i ≤ s ) and some j (1 &lt; j ≤ l ), then d u ( 1 ,j , w ) = d u ( i,j , w ) for all w ∈ W \ { u i,j } , thus the code of u 1 ,j ∈ P 1 and the code of u i,j ∈ W with respect to W differ by one coordinate only, which is contradiction that W is WTMB of G . Thus W ∩ V ( P i ) = ∅ for each i (1 ≤ i ≤ s ). Moreover l &lt; l i for each i where ( s &lt; i ≤ t ), so by Proposition 23, W must contain at least one vertex from remaining t -s branches of v . Also W is a WTMB of G if | W ∩{ V ( P i ) : 1 ≤ i ≤ }| t is minimum which is possible only when we take exactly one vertex from each P i (1 ≤ i ≤ t ).

Corollary 26. Let G be a non-path tree and v be an exterior major vertex of G with t branches and v does not have the unique branch of shortest length, then dim( G ) ≥ t -1 and dim wt ( G ) ≥ t .

Corollary 27. Let G be a non-path tree and W ⊆ V ( G ) where W = { u k i,j ∈ P k i for each k (1 ≤ k ≤ ex G ( )) and each i (1 ≤ i ≤ t k ) and at least one j (2 ≤ j ≤ l k i ) } , then W is WTR-set for G .

It was shown by Chartrand et al. in [5] that dim( G ) = σ G ( ) -ex G ( ) for a non-path tree G . Let µ ≥ 0 denotes the number of exterior major vertices of G which do not have the unique branch of shortest length. The next result provide the weak total metric dimension of a tree.

Theorem 28. Let G be a non-path tree, then dim wt ( G ) = dim( G ) + µ .

Proof. Since every WTR-set is a resolving set, so inequality 1, Proposition 23 and Corollary 26, yield dim wt ( G ) ≥ dim( G ) + µ . For dim wt ( G ) ≤ dim( G ) + µ , let { v k : 1 ≤ k ≤ ex G ( ) } be the set of exterior major vertices of G and each v k has t k number of branches P k i and each branch P k i has l k i number of vertices. We label v k is ascending order of k such that v k : (1 ≤ k ≤ µ ) do not have the unique branch of shortest length and v k : ( µ &lt; k ≤ ex G ( )) have the unique branch of shortest length P k 1 . Let B be a metric basis of G and by Remark 22, B contains at least one vertex from at least t k -1 branches of v k . We choose one vertex from branch P k i for each i (1 ≤ i ≤ t k -1) and each k (1 ≤ k ≤ µ ) other than v k and one vertex from branch P k i for each i (2 ≤ i ≤ t k ) and each k ( µ &lt; k ≤ ex G ( )) other than v k . By Theorem 24 and Theorem 25, W = B ∪{ u k t k ,l k t k : 1 ≤ k ≤ µ } is a WTMB of G . It concludes the proof.

Theorem 29. Let G be a non-path tree. Then dim wt ( G ) = 2 if and only if every exterior major vertex of G has at most three branches in which one is the unique branch of shortest length and one of the followings hold:

- (1) G has exactly one exterior major vertex with three branches and no exterior major vertex with two branches.

(2) G has exactly two exterior major vertices with two branches and no exterior major vertex with three branches.

Proof. Given that G is a non-path tree. Let dim wt ( G ) = 2, since only a path has metric dimension one [11], so inequality (1) implies that dim( G ) = dim wt ( G ) = 2 and hence µ = 0. Thus all exterior major vertices of G has the unique branch of shortest length. Suppose G has an exterior major vertex with td v ( ) ≥ 4, then by Theorem 24, dim wt ( G ) ≥ 3. Thus every exterior major vertex of G has at most three branches. We discuss the following two cases:

/negationslash

Case 1: td v ( ) ≤ 2 for all exterior major vertices v . If G has an exterior major vertex with terminal degree 2, then there are two such vertices v 1 , v 2 each has two branches P k 1 , P k 2 k = 1 2 , with P k 1 as the unique branch of shortest length of v k for each k = 1 2 and by Theorem 24, , dim wt ( G ) = 2. Suppose G has another exterior major vertex u (= v , v 1 2 ) with td u ( ) = 2, then by Theorem 24, dim wt ( G ) ≥ 3 .

Case 2: td v ( ) ≤ 3 for all exterior major vertices v . If G has an exterior major vertex v with td v ( ) = 3, then v is the only vertex with td v ( ) = 3 and v has exactly three branches P , P , P 1 2 3 in which P 1 is the unique branch of shortest length, and hence by Theorem 24, dim wt ( G ) = 2. Suppose G has another vertex u with td u ( ) = 3 or td u ( ) = 2, then in both cases dim wt ( G ) ≥ 3 by Theorem 24.

The converse part of the theorem is obvious.

The following result provides the realization of weak total metric dimension in some graphs G of order n .

Theorem 30. For every two integers a, b with 2 ≤ a ≤ b , there exists a graph G of order b with dim wt ( G ) = a .

Proof. For a = b , let G be a graph of order b in which each vertex is twin. Then Theorem 13, concludes that dim wt ( G ) = b = a . Now, consider a ≤ b -1. Consider a path P b -a +1 and let one leaf of this path be l . Attach a -1 leaves l 1 , l 2 , . . . , l a -1 with the leaf l . Call the resultant graph G of order b . For a ≥ 3, G is a non-path tree with exactly one exterior major vertex l with td l ( ) = a in which a -1 are twin leaves. Then µ = 1. Also dim( G ) = a -1, by a result of Chartrand et al. given in [5]. Thus, Theorem 28 implies that dim wt ( G ) = a . For a = 2, G is a path P b vertices and it is straightforward to see that the set of two leaves of P b is a WTMB of G .

We define a notion which is useful for finding an upper bound on weak total resolving number of a non-path tree.

$$\theta ( G ) = \min _ { ( 1 \leq i \leq t _ { k } ), ( 1 \leq k \leq e x ( G ) ) } l _ { i } ^ { k }$$

For instance, if a tree has twin leaves, then θ = 2.

Proposition 31. Let G be a non-path tree of order n ≥ 4 and W ⊆ V ( G ) with cardinality n -θ G ( ) + 2 , then W contains at least one vertex from branch P k i of an exterior major vertex v k other than v k , for each i (1 ≤ i ≤ t k ) and each k (1 ≤ k ≤ ex G ( )) where t k , P k i as define earlier.

Proof. Let G be a non-path tree in which n -θ G ( ) + 2 is smallest. Also n -θ G ( ) + 2 is smallest when n is smallest and θ G ( ) is largest. Such a tree contains only one exterior major vertex v 1 (if G has more than one exterior major vertices then n is not smallest) and v 1 have only three similar

branches P 1 1 , P 1 2 , P 1 3 (if G has more than three branches or branches are not similar, then n is not largest as compared to θ G ( )) and each branch has l 1 is number of vertices. Then n = 3 l 1 -2 and θ G ( ) = l 1 and n -θ G ( ) + 2 = 2 l 1 . Number of vertices (including v 1 ) in two any two branches say P 1 1 , P 1 2 is 2 l 1 -1. Thus any set W ⊆ V ( G ) of 2 l 1 vertices contains at least one vertex from third branch P 1 3 other than v 1 .

Theorem 32. Let G be a non-path tree of order n ≥ 4 , then res wt ( G ) ≤ n -θ G ( ) + 2 .

Proof. Let W ⊆ V ( G ) with cardinality n -θ G ( ) + 2, then by Proposition 31, W contains at least one vertex from all branches of all exterior major vertices of G other than exterior major vertices and hence by Corollary 27, W is a WTR-set. It concludes the proof.

By Proposition 23, Corollary 26 and Theorem 28, we have the following proposition for a lower bound on the weak total resolving number of a non-path tree.

Proposition 33. Let G be a non-path tree of order n with p exterior major vertices v , v 1 2 , . . . , v p each has t k branches of length l k i -1 (1 ≤ k ≤ p ; 1 ≤ i ≤ t k ) . Then

$$\sum _ { k = 1 } ^ { p } \sum _ { i = 1 } ^ { t _ { k } } ( l _ { i } ^ { k } - 1 ) \leq r e s _ { w t } ( G ).$$

Consider two vertices x and y such that x ∼ y . Take four paths P r ≥ 3 : x , x 1 2 , . . . , x r ; P ′ r : x , x ′ 1 ′ 2 , . . . , x ′ r ; P 3 : y , y 1 2 , y 3 and P ′ 3 : y , y ′ 1 ′ 2 , y ′ 3 . Identify the vertex x with the leaves x , x 1 ′ 1 and identify the vertex y with the leaves y , y 1 ′ 1 . The resultant graph G is a non-path tree with two exterior major vertices x = x 1 = x ′ 1 and y = y 1 = y ′ 1 each has two similar branches. Clearly, µ = 2 and so dim wt ( G ) = 4, by Theorem 28. Note that p = 2, t 1 = 2 , t 2 = 2 and so p ∑∑ k =1 =1 t k i ( l k i -1) = 2( r +1). We claim that res wt ( G ) = 2( r +1). It is a routine exercise to see that any set of cardinality 2( r +1) is a WTR-set for G . Indeed, if we say that res wt ( G &lt; ) 2( r +1), then the set ( V ( P r ) -{ x 1 } ) ∪ ( V ( P ′ r ) -{ x ′ 1 } ) ∪{ x, y } ∪ { v } , where v ∈ V ( P 3 ) -{ y 1 } or v ∈ V ( P ′ 3 ) -{ y ′ 1 } , is not a WTR-set for G , by Corollary 26. It concludes that res wt ( G ) = p ∑∑ k =1 =1 t k i ( l k i -1).

From Proposition 33 and Theorem 32 we have following theorem.

Theorem 34. Let G be non-path tree, then

$$\sum _ { k = 1 } ^ { p } \sum _ { i = 1 } ^ { t _ { k } } ( l _ { i } ^ { k } - 1 ) \leq r e s _ { w t } ( G ) \leq n - \theta ( G ) + 2.$$

## References

- [1] Chappell, G., Gimbel, J., Hartman, C.: Bounds on the metric and partition dimensions of a graph. Ars Combin. 88, 349-366 (2008).
- [2] Chartrand, G., Poisson, C., Zhang, P.: Resolvability and the upper dimension of graphs. Comp. Math. Appl. 39(12), 19-28 (2000).

- [3] Chartrand, G., Salehi, E., Zhang, P.: The partition dimension of a graph. Aequationes Math. 59(1-2), 45-54 (2000).
- [4] Chartrand, G., Zhang, P.: On the chromatic dimension of a graph. Congr. Numer. 145, 97-108 (2000).
- [5] Chartrand, G. Eroh, L., Johnson, M.A., Oellermann, O.R.: Resolvability in graphs and the metric dimension of a graph. Disc. Appl. Math. 105(1-3), 99-113 (2000).
- [6] Cockayne, E.J., Dawes, R.M., Hedetniemi, S.T.: Total domination in graphs. Networks. 10, 211-219 (1980).
- [7] Gary, M.R., Johnson, D.S.: Computers and Intractibility: A guide to theory of NPcompleteness. Freeman, New York (1979).
- [8] Harary, F., Melter, R.A.: On the metric dimension of a graph. Ars Combin. 2, 191-195 (1976).
- [9] Hernando, C., Mora, M., Slater, P.J., Wood, D.R.: Fault-Tolerant metric dimension of graphs. Proc. Internat. Conf. Convexity in Discrete Structures, Ramanujan Math. Society Lecture Notes. 5, 81-85 (2008).
- [10] Javaid, I., Iftikhar, F., Salman, M.: Total resolvability in graphs. Middle-East Journal of Scientific Research. 11, 1649-1658 (2012).
- [11] Khuller, S., Raghavachari, B., Rosenfeld, A.: Landmarks in graphs. Disc. Appl. Math. 70, 217-229 (1996).
- [12] Khuller, S., Raghavachari, B., Rosenfeld, A.: Localization in graphs. Technical Report CSTR-3326, University of Maryland at College Park (1994).
- [13] Melter, R.A., Tomescu, I.: Metric bases in digital geometry. Computer Vision, Graphics and Image Processing. 25, 113-121 (1984).
- [14] Slater, P.J.: Leaves of trees. Congr. Numer. 14, 549-559 (1975).
Imran Javaid Muhammad Salman Mahr Murtaza Farheen Iftikhar Muhammad Imran
Weak total resolving sets in graphs
A set $W$ of vertices of $G$ is said to be a weak total resolving set for $G$
if $W$ is a resolving set for $G$ as well as for each $w\in W$, there is at
least one element in $W-\{w\}$ that resolves $w$ and $v$ for every $v\in V(G)-
W$. Weak total metric dimension of $G$ is the smallest order of a weak total
resolving set for $G$. This paper includes the investigation of weak total
metric dimension of trees. Also, weak total resolving number of a graph as well
as randomly weak total $k$-dimensional graphs are defined and studied in this
paper. Moreover, some characterizations and realizations regarding weak total
resolving number and weak total metric dimension are given.