# Metric Dimension Threshold of Graphs

Authors: Meysam Korivand; Kazem Khashyarmanesh; Mostafa Tavakoli
Journal: Journal of Mathematics
 (2022)

---

## Abstract

LetG be a connected graph. A subset S of vertices of G is said to be a resolving set of G, if for any two vertices u and v of G there is at least a member w of S such that du,w≠dv,w. The minimum number t that any subset S of vertices G with S=t is a resolving set for G, is called the metric dimension threshold, and is denoted by dimthG. In this paper, the concept of metric dimension threshold is introduced according to its application in some real-word problems. Also, the metric dimension threshold of some families of graphs and a characterization of graphs G of order n for which the metric dimension threshold equals 2, n−2, and n−1 are given. Moreover, some graphs with equal the metric dimension threshold and the standard metric dimension of graphs are presented.


---

## Body

## 1. Introduction

Throughout this paper, all graphs considered are assumed to be finite, simple, undirected, and connected. For a graphG, the vertex set and the edge set of G are denoted by VG and EG, respectively. We remind that all notations and terminologies are standard here and taken mainly from the standard books of graph theory. For instance as usual, we denote the path, the cycle, the star, and the complete graph on n vertices by Pn, Cn, Sn, and Kn, respectively. The distance between two vertices u and v, denoted by dx,y, is the number of edges in a shortest path from u and v. Let G be a graph with v∈VG. The eccentricity ev is the distance between v and a vertex farthest from v in G. The diameter diamG of G is the greatest eccentricity among the vertices of G. For an ordered subset S=v1,v2,…,vk of vertices and a vertex v in a connected graph G, the metric S-representation of v is the vector rv|S=dv,v1,…,dv,vk. The set S is a resolving set for G if every two vertices of G have distinct S-representations. Particularly, a vertex w∈VG resolves a pair of vertices v,u∈VG if dv,w≠du,w. The minimum cardinality of a resolving set of G is called metric dimension of G and denoted by dimG. This concept was first introduced by Slater in 1975 [22]. To see more details about metric dimension of graphs, we recommend references [2, 5, 9, 26].Also, several versions of the standard metric dimension have been introduced and studied. In the following, we will discuss some of these versions.In 2004, Sebö and Tannier introduced and studied a stronger version of the standard metric dimension which is called the strong metric dimension [21]. In the standard metric dimension, a resolving set uniquely specifies the position of vertices; however, this set cannot distinguish distances in the graph. Sebö and Tannier’s goal was to introduce a set called a strong resolving set so that in addition to vertices, they also distinguish distances. For the sake of it, they said, one vertex a strongly resolves vertices b and c, if there exist the smallest path between b( respectively c) and a such that c( respectively b) belongs to the path. As well, in [11], Okamoto et al. introduced a special version of the standard metric dimension. In this way, instead of all vertices in the standard metric dimension, only adjacent vertices have a different representation from the metric generator. The cardinality of the smallest set which resolves every two adjacent vertices is called the local metric dimension. Researchers have had significant results on this concept. Among the interesting correlations obtained between the local metric dimension and the independent set, it is shown that n−βG is an upper bound for the local metric dimension of a graph G with order n. The classification of graphs that apply to the above boundary equation is still open. For more results, the reader can refer to papers [4, 17, 24].In addition, other versions of the metric dimension had been introduced, includingk-metric dimension, adjacency dimension, resolving partitions, edge metric dimension, mixed metric dimension, and fractional metric dimension [1, 7, 8, 13–15].Graph theory has many applications in various sciences, including chemistry, to study some related parameters: see, for example, [18, 19]. Also, there are many applications for this invariant including error correcting codes, robot navigation, privacy in social networks, chemistry, pattern recognition, coin weighing, image processing, and locating intruders in networks [3, 5, 6, 12, 16, 20, 22, 25]. In situations where the points in the (submarine, drone, etc.) robot’s movement space are fixed and without damage, a metric generator set S is used to locate the robot (submarine, drone, etc.). Now, consider the situation in which the points in the robot movement space are vulnerable. In this case, some vertices of S could damage and unusable. Therefore, there is a need to replace S with another metric generator set such as S′. On the other hand, the problem of finding a metric generator set is NP-hard, and as a result, finding S′ takes a long time. This reason inspired us to use the following concept in such situations.For any connected graphG, we define metric dimension threshold, denoted by dimthG, to be the minimum number t such that any subset S of vertices G with S=t is a resolving set for G. In this paper, we determine the metric dimension threshold for some well-known family of graphs. We also characterize graphs G of order n for which dimthG is equal to 2, n−2, or n−1. Finally, we present some graphs G with the property that dimG=dimthG.


## 2. Basic Results

In this section, we determine the metric dimension threshold of paths, cycles, and the Petersen graph. Also, we characterize all graphsG with order n such that dimthG=n−1 or n−2.Clearly, for every connected graphG with order n, we have dimG≤dimthG≤n−1. It is especially suitable for the robot if the resolving set S is of size dimG. In fact, finding the graph G with the property that dimG=dimthG is on attention.Remarks 1.
LetG be a connected graph.(i)
Letrbe a positive integer. For every subsetS⊆VGwithS=r, we haverv|S≠ru|S, forv,u∈VG, and then, for everyS⊆VGwithS≥r, we haverv|S≠ru|S, forv,u∈VG.(ii)
Assume thatdimthG=k. Then, it follows from (i) that any subsetSof vertices ofGwithS≥kis resolving.For a vertexa of G, we use Na to denote the set of its neighbours. Also, for a set S of vertices of graph G, we set NS=∪a∈SNa.Theorem 1.
For anyn≥3, we have dimthPn=2.Proof.
At first, we claim thatdimthPn≠1. To see this, we consider the set S:=Na, where a is a pendant vertex in Pn. It is not hard to see that S is not a resolving set of Pn.
LetS:=a,b be an arbitrary subset of vertices of Pn with two elements. Since the set included a pendant vertex of Pn is a resolving set, we may assume that a and b are not pendant vertices. Consider arbitrary vertices v and u of Pn, and assume that dv,a=du,a=k. Let P and P′ denote the paths between a and the pendant vertices Pn. Clearly, both v and u cannot belong to P or P′. Without loss of generality, we may assume that v∈P, and u∈P′. Suppose that b∈P. If b belongs to the path between v and a, via Pv, we have dv,b<k<du,b. Otherwise, in the case that b∉Pv, we have du,b=2k+dv,b. This means that dv,b≠du,b, for any position of b. Therefore, rv|S≠ru|S, and the proof is complete.Corollary 1.
LetGbe a graph. Then,dimthG=1if and only ifG∈P1,P2.Theorem 2.
For each integern≥2, we havedimthCm=3,ifm=2n,2,ifm=2n−1.Proof.
Assume first thatm=2n. We claim that dimthCm≠2. To see this, suppose that S:=a,b, for some vertices a and b of G with da,b=n. Then, Na=v,u, and so rv|S=ru|S.
In the following, we show thatdimthCm=3. To achieve this, let S=a,b,c be an arbitrary subset of the vertices of Cm. Also, assume that v and u are arbitrary vertices of Cm such that dv,a=du,a and dv,b=du,b. Thus, da,b=dv,a+dv,b. Suppose the path between a and b includes v (respectively, u) are denoted by Pv (respectively, Pu). We have VPv∪VPu=VCm and VPv∩VPu=a,b. Hence, c∈VPv or c∈VPu. In any cases, it is easy to check that dv,c≠du,c. Therefore, rv|S≠ru|S.
Now, letm=2n−1, and S=a,b be an arbitrary subset of vertices of Cm. Suppose that dv,a=du,a for some vertices u and v of Cm. By using a method similar to that we used in to above paragraph, one can easily check that dv,b≠du,b. Hence, rv|S≠ru|S. Since dimCm=2, we have dimthCm=2, which completes the proof.Recall that, the Kneser graphKGr,s is the graph whose vertices are in a 1–1 correspondence with the r-sized subsets of 1,2,3,…,s, and there is an edge between two vertices if their corresponding r-subsets are disjoint [10]. The Petersen graph KG2,5 has shown in Figure 1.Figure 1
The Petersen graphKG2,5.Theorem 3.
IfPis the Petersen graph, thendimthP=5.Proof.
Consider the subsetS:=1,2,3,4,1,5,2,5 of vertices of P. Then, rv|S=ru|S, where v=3,5 and u=4,5. This implies that dimthP>4.
Suppose thatS=v1,v2,…,v5 is a subset of P, which is not a resolving set for P and seeks a contradiction. Since diamP=2, two vertices u and v can be selected in the following cases:(i)
Case 1.dv,u=2. Since P is a 3-arc transitive graph [10], without loss of generality, we may assume that v=1,2 and u=1,3. Suppose that w is an arbitrary vertex of P. If dw,u=1=dw,v, then it is easy to see that w=4,5. Otherwise, we have dw,u=2=dw,v. Now, when 1∈w, we have w=1,4 or w=1,5. Also whenever 1∉w, we have w=2,3. The only common neighbour of v and u is 4,5. Assume that v1=4,5, and we are looking for elements for which there are other candidate members for S. Members of S must be selected with the following conditions:(1)vi∩v≠∅andvi∩u≠∅;2≤i≤4.(i)
Thus,1∈vi or 2,3∈vi, for 2≤i≤5. The vertices obtained in this way are v2=1,4, v3=1,5, and v4=2,3. Now, any other vertex that we consider as v5 resolves vertices v and u, which is a contradiction.Case 2.dv,u=1. In this situation, by using a method similar to that we used in Case 1, one can obtain a contradiction.Theorem 4.
LetGbe a connected graph of ordern≥3. Then,dimthG=n−1if and only if there exist verticesvanduofGsuch thatNv−u=Nu−v.Proof.
⇒ Assume that dimthG=n−1. Then, there exist two vertices v and u of G such that VG−v,u is not a resolving set. Hence, the distance of v and u from vertices of VG−v,u is the same. We claim that there exists a vertex w with u≠w in VG such that w is adjacent to v. To achieve this aim, suppose that, for any vertex w with u≠w in VG, we have w≁v and seek a contradiction. Since G is a connected graph, we have v∼u. Thus, for any vertex x∈VG−v,u, we have dx,v=dx,u+1 which is a contradiction. This means that Nv−u≠∅. Since the distance of any vertex of Nv−u from v is 1, we have Nv−u=Nu−v.
⇐ Assume that there exist vertices v and u of G such that Nv−u=Nu−v. Clearly, VG−v,u cannot be a resolving set of G. Thus, VG−v,u<dimthG. Therefore, dimthG=n−1, and the proof is complete.The following corollaries are immediate from Theorem4.Corollary 2.
There is an infinite number of graphGwithdimthG=n−1.Corollary 3.
LetGbe a complete multipartite graph with ordern. Then, dimthG=n−1.Corollary 4.
LetGbe a graph with ordern. Then, dimG=dimthG=n−1if and only ifG≅Kn.The partitionV0,V1,…,Vev of VG is called a distance partition with reference to the vertex v if V0=v and Vi contain those vertices which are at distance i from v for 0≤i≤ev. The sets V0,V1,V2,…,Vk are called distance partite sets.Theorem 5.
LetGbe a graph with ordern≥4. Then, dimthG=n−2if and only ifGsatisfies in the following conditions:(a)
(a1)
There exist verticesv,u, andwofGsuch thatw∈Nv(a2)
Nv−u,w=Nu−v(a3)
The vertexwis a pendant vertex orw∈NVi,NVjfor1≤i≤2and3≤j≤eu, whereVis are the distance partite sets ofGVG−v,wreference tou(b)
For any verticesvandu,Nv−u≠Nu−v.Proof.
IfdimthG=n−2, then there exist vertices v,u, and w of G with property that A=VG−v,u,w is not a resolving set. Thus, there exist two vertices of u,v,w with the same A-representation. Assume that rv|A=ru|A. Since the set VG−v,u must resolves vertices v and u, we have dv,w≠du,w. Suppose that Nw∩v,u=∅. Then, Nw⊆A. For every w′∈Nw, since w′∈A, we have dv,w′=du,w′. This implies that dv,w=du,w which is a contradiction. Similarly, it is impossible to have v,u⊆Nw. Hence, v∈Nw and u∉Nw.
For (a2), it is enough to show thatNv∩Nu≠∅. Assume that Nv∩Nu=∅, and we seek a contradiction. Since G is connected, we may have a vertex x∈A∪v such that x∈Nu. If Nu=v, then, for any member of A, as x, we have dx,u=dx,v+1, a contradiction. Otherwise, if Nu≠v, then there exists a vertex y∈A such that y∈Nu. Thus, y∉Nv. Hence, y resolves vertices v and u, which is a contradiction.
For (a3), suppose thatw is not a pendant vertex. Hence, w has some neighbours in A, and so it is easy to show that w is not a member of Nv∩Nu. However, if w∈NV1∖NVj or w∈NV2∖NVj, for 3≤j≤eu, one can see that the vertices in A keep their distance from v and u. Suppose, contrary to our claim, that w∈NVi, for an integer i with 3≤i≤eu. Then, there exists vertex z∈Vi such that w is adjacent to z. Now, if i=3, then dz,u=3. Since dz,v=2, we have dy,u≠dy,v, which is impossible. If i≥5, then the smallest path between u and z contains v. Thus, z resolves v and u, a contradiction. If i=4, then we have two cases. First, suppose that v is adjacent to u. Then, dz,u=3, and so dz,u≠dz,v. Finally, if v is not adjacent to u, one can check that dz,u=4. Therefore, in both cases, A is a resolving set, whenever w∈NVi, for 3≤i≤eu, which is a contradiction.
For the converse, assume thatG satisfies the conditions (a) and (b). In view of Theorem 4, the statement (b) implies that dimthG<n−1. Let A=VG−v,u,w be the subset of vertices G, where v,u, and w are the vertices described in (a). One can easily check that rv|A=ru|A. This implies that dimthG>n−3. Hence, dimthG=n−2, and the proof is complete.Now, we consider the family of graphsG of order n with the property that dimthG=n−2. Clearly, the smallest one is P4. For a positive integer k, let Gk be the graph with VGk=a1,a2,…,ak∪v,u,w and EGk=a1v,a2v,…,akv∪a1u,a2u,…,aku∪vw. By matching Gk to G in the previous theorem, one can check that dimthGk=k+1. Thus, we have the following corollary.Corollary 5.
There are an infinite number of graphsGwithdimthG=n−2.For verticesv and u of a graph G, we shall use Fv,u to denote the set of those vertices w∈VG with the property that dw,u=dw,v. Now, we define FG to be the greatest Fv,u for u,v∈VG. Hence,(2)FG=maxv,u∈GFv,u.One can easily check that1≤FG≤n−2. In the next theorem, we present a lower bound for dimthG in terms of FG.Theorem 6.
LetGbe a graph. Then,FG+1≤dimthG.Proof.
Suppose thatFG=Fv,u, for vertices v and u of G. Since the set Fv,u does not resolve vertices v and u, the result follows.It is obvious that the above upper bound is sharp. For instance, ifPn is a path of length n, then FG+1=dimthG=2. Moreover, all graphs G with the property that dimthG=n−1 satisfy in the equality FG=n−2. In fact, Theorem 4 states that FG=n−2 if and only if dimthG=n−1. So, in view of the previous theorem, we can express the following proposition.Proposition 1.
LetGbe a graph withFG=n−3. Then,dimthG=n−2.


## 3. Graphs withdimGdimthG

In Corollary4, we show that the only graph G of order n with dimG=dimthG=n−1 is the complete graph Kn. In this section, we want to investigate graphs G of order n with the property that dimG=dimthG=k, for k∈2,n−2. Moreover, we characterize all graphs G with dimthG=2.Graphs with metric dimension two were studied by Sudhakara and Hemanth Kumar in [23]. Also, Chartrand et al. [6] provided a characterization of graphs of order n and metric dimension n−2. In the following, we will use the results in [6, 23] to obtain a characterization of graphs G of order n with dimG=dimthG∈2,n−2.Theorem 7 [6, Theorem 4].
LetGbe a connected graph of ordern≥4. Then,dimG=n−2if and only ifG=Ks,ts,t≥1,G=Ks+Kt¯s≥1,t≥2, orG=Ks+K1∪Kts,t≥1.Theorem 8.
IfGis a graph with ordern≥4anddimG=n−2, thendimthG=n−1.Proof.
LetG=Ks,ts,t≥1, or G=Ks+Kt¯s≥1,t≥2. Then, G is a multipartite graph and dimthG=n−1.
Now, assume thatG=Ks+K1∪Kts,t≥1. If s=t=1, then n<4, which is a contradiction. Suppose that s≥2 or t≥2. Without loss of generality, we may assume that s≥2. Hence, for two arbitrary vertices a,b∈VKs, we have Nv−u=Nu−v. Thus, by Theorem 4, dimthG=n−1.Corollary 6.
There is no graphGof ordernwith property thatdimG=dimthG=n−2.Theorem 9 [23, Theorem 6.1].
LetGbe a graph which is not a path withVG=v1,v2,…,vnandVi0,Vi1,…,Vikibe the distance partition ofVGwith reference to the vertexviwherekiis the eccentricity ofvi,1≤i≤n. The metric dimension ofGis 2 if and only if there exist verticesviandvjsuch thatVik∩Vjℓ≤1for everykandℓwith1≤k≤eviand1≤ℓ≤evj.Lemma 1.
LetGbe a graph withVG=v1,v2,…,vnandVi0,Vi1,…,Vievibe the distance partition ofVGwith reference to the vertexvi. For everyviandvj1≤i,j≤n, andkandℓwith1≤k≤eviand1≤ℓ≤evj, we haveVik∩Vjℓ≤1if and only ifG∈Pn,C2n−1, for an≥2.Proof.
Only one implication requires proof. Suppose thatG is a graph of order n≥4. We claim that degvi≤2, for every i with 1≤i≤n. Suppose, contrary to our claim, that there exists i with 1≤i≤n such that degvi>2. Let Nvi=v1,v2,v3. Then, Nvi⊆Vi1. We need to consider the following four cases for GNvi.Case 1.GNvi=K3¯. Thus, v1,v2⊆V32. This implies that Vi1∩V32>1, which is a contradiction.Case 2.GNvi=K2∪K1. Suppose that v1 is adjacent to v2. Hence, v1,v2⊆V32. So we have Vi1∩V32>1, which is a contradiction.Case 3.GNvi=P3. Without loss of generality, we may assume that v1,v2⊆Nv3. This means that Vi1∩V31>1, again, which is a contradiction.Case 4.GNvi=K3. In this situation, similar to that used in Case 3, one can obtain a contradiction.
So, for anyi with 1≤i≤n, we have degvi≤2. This implies that G is isomorphic to Pn or Cn, for some positive integer n.
In the following, we show that ifG≅Cn, then n is an odd integer. On the contrary, suppose that G≅C2k, for an integer k with k≥2. Assume that EC2k=v1v2,v2v3,…,v2k−1v2k,v2kv1 and that dv1,vk+1=diamG. Thus, Nv1=v2,v2k and dvk+1,v2=dvk+1,v2k=k−1. Therefore, V11∩Vk+1k−1>1, which is a contradiction, and the proof is complete.Theorem 10.
LetGbe a graph. Then,dimthG=2if and only ifGis isomorphic to one of the graphsPnorC2n−1, for a positive integern≥2.Proof.
LetVG=v1,v2,…,vm. First, we suppose that G is isomorphic to one of the graphs Pn or C2n−1, for a positive integer n≥2. By Lemma 1, each vi and vj1≤i,j≤m, k and ℓ with 1≤k≤evi and 1≤ℓ≤evj, implies that Vik∩Vjℓ≤1. By the way of contradiction, assume that there exist vi and vj1≤i≤m and k,ℓ which 1≤k≤evi and 1≤ℓ≤evj such that Vik∩Vjℓ>1. Hence, there exist distinct vertices u1 and u2 in Vik∩Vjℓ. Since u1,u2∈Vik and u1,u2∈Vjℓ, we have du1,vi=du2,vi=k and du1,vj=du2,vj=ℓ. This means that set vi,vj can not to be a resolving set of G, which is a contradiction.
The converse implication follows almost immediately from Theorems 1 and 2.The next corollary is obtained from Theorem10, [6, Theorem 2], and Theorem 2.Corollary 7.
LetGbe a graph. Then,dimG=dimthG=2if and only ifG≅C2n−1, for a positive integern≥2.We end the paper with the following problem.Open Problem. Let k be a positive integer 3≤k≤n−3. Characterize the class of graphs G with the property that dimG=dimthG=k.



---

*Source: 1838719-2022-09-14.xml*