# Computing Fault-Tolerant Metric Dimension of Connected Graphs

Authors: Uzma Ahmad; Sara Ahmed; Muhammad Javaid; Md Nur Alam
Journal: Journal of Mathematics
 (2022)

---

## Abstract

For a connected graph, the concept of metric dimension contributes an important role in computer networking and in the formation of chemical structures. Among the various types of the metric dimensions, the fault-tolerant metric dimension has attained much more attention by the researchers in the last decade. In this study, the mixed fault-tolerant dimension of rooted product of a graph with path graph with reference to a pendant vertex of path graph is determined. In general, the necessary and sufficient conditions for graphs of order at least 3 having mixed fault-tolerant generators are established. Moreover, the mixed fault-tolerant metric generator is determined for graphs having shortest cycle length at least 4.


---

## Body

## 1. Introduction

The concept of metric dimension is applicable in all those networks where there is a need of localization of particular nodes. It is significantly used in different fields of science such as telecommunication, road networking, chemistry, and image processing to find winning combinations for different games. Slater in 1975 [1] introduced the locating set of graphs, whereas, in 1976, Harary and Melter [1] defined the term resolving set for graphs. Later on, both the terms were emerged and named as metric-based basis or generator. For a graph, J,W⊆VJ is termed as metric generator if for a,b∈VJa≠b, there exists a vertex w∈W, such that da,w≠db,w. Then, the vertex w∈W is said to distinguish (resolve) vertices a and b. If W=w1,…,ws, then the distance coordinate vector of a∈VJ is s-tuple ra|W=da,w1,…,da,ws. This metric generator is extensively studied in literature.The behavior of metric dimension of graphs relative to different graph products was investigated by different authors, like Cartesian product by Caceres et al. [2], the join product as well as Cartesian product by Hernando et al. [3], and join of different combinations of complete, path, cycle graphs by Sunitha et al. [4]. Even though metric generator was first proposed for problem of robot navigation, now this metric generator along with its various variants can have interesting and significant connections to other fields as well. For example, the determination of local variant named as local metric dimension may be associated to limited function of robot sensors. The mixed metric generator is one of the variants of the metric generator. This mixed version of metric generators was presented in 2017 by Kelenc et al. [5]. A subset M⊆VJ is termed as the mixed metric generator of graph J if coordinate distance vectors relative to M of any two distinct elements of VJ∪EJ are not same. The smallest set which is the mixed generator of graph J is termed as mixed basis, and its cardinality is termed as mixed dimension dimJ. Kelenc et al. [5] showed that a necessary and sufficient condition for a graph J of order r to have mixed dimension two is J≅Pr. They also proved that dimCn=3 and dimPr2□Pr2=3 for r1≥r2≥2.Hernando et al. [6] in 2008 presented the idea of the fault-tolerant metric (FTM) generator. To illustrate this, consider a network where the metric basis represents the censors [7]. In this situation, if some censor is forced to not operate properly, then other censors will not be sufficient to localize all stations or places uniquely and to deliver proper information to confront the problem. This type of frequently occurring situation in networks was resolved by Hernando et al. [6] with the help of applying fault-tolerance in the metric generator. To consider the fault-tolerance in the metric generator, the new generator will be able to transfer the information correctly even when a censor is disabled for any reason. It can be said that this FTM generator is applicable to all those networks where metric dimension has its significance like in optimal flow control problems of interconnecting networks.The FTM generator and FTM dimension for a tree was determined in [6]. Javaid et al. [8] also explored the FTM dimension and FTM partition dimension of different graphs. They exhibited that for a graph of order m,m≤PDn−2m, where P is the fault-tolerant partition dimension and D is the diameter of the graph. The FTM dimension of infinite families of convex polytopes is proved to be constant by Raza et al. [9]. So far, a lot of research works on metric dimension and its different variants have been carried out by different authors, whereas comparatively less investigations have been made in the exploration of mixed generators. The motivation of this research work is to fill this literature gap and to apply the concept of fault-tolerance in mixed generators.


## 2. Mixed Dimension of Rooted Product

The rooted productQ1⊳oQ2 can be constructed by taking connected graphs Q1 and Q2 and a root vertex o∈Q2 such that V(Q1 o Q2) = {(a1, b1)|a1 ∈ V(Q1), b1 ∈ V(Q2)} and E(Q1 o Q2) = {(a1, b1)(a2, b2)|a1 = a2 & b1 ∼ b2 or b1 = b2 = o & a1 ∼ a2}.Corollary 1.
(see [10]). A pendant vertex always belongs to every mixed metric generator of the graph.Theorem 1.
Consider a graphQ having order n ≥ 2. If o is the pendant vertex of Pm, then dimmQ′=Q⊳oPm=n.Proof.
LetVQ=p1,p2,…,pn and S=w1,w2,…,wk be the mixed metric basis of Q. Also, suppose that VPm=q0,q1,…,qm−1, such that q0 and qm−1 are the pendant vertices and EPm=qiqi−1:1≤i≤m−1. To construct required Q′=Q⊳oPm, take the vertex o=q0. The vertex set and edge set of Q′=Q⊳oPm are given as VQ′=pi,qj:1≤i≤n,0≤j≤m−1 and EQ′=pi,qj−1pi,qj,pi,opj,o:pipj∈EQ. Clearly, the set of pendant vertices of Q′ is M=pi,qm−1:1≤i≤n. If S∗ is the mixed metric generator of Q′, then from Corollary 1, M=pi,qm−1:1≤i≤n⊆S∗. Hence,(1)dimmQ′=Q⊳oPm≥n.
LetX=pi,qj,pi,qj−1pi,qj:1≤i≤n,1≤j≤m−1⊆Q′. Then, Q=Q′−X. Now, we prove that M is a mixed metric generator. For this, let g,h∈Q′. Then, there arise three cases.Case 1.
Letg,h∈X. If g=pi,qkrespectivelypi,qk−1pi,qk and h=pj,qkrespectivelypj,ql−1pj,ql, such that i≠j; then, dg,pi,qm−1=t<m,dh,pi,qm−1≥m. If g=pi,qk and h=pj,ql−1pj,qli≠j, then dg,pi,qm−1<m,dh,pi,qm−1≥m. If g=pI,qk and h=pi,ql−1pi,qlk≠l, then clearly, dg,pi,qm−1≠dh,pi,qm−1. But if g=pi,qk and h=pi,qk−1pi,qk, then dg,pi,qm−1=dh,pi,qm−1. Now, as n ≥ 2, there exist j≠i, such that pj,qm−1∈X. But as pi,qk−1 is nearer to pj,qm−1 as compared to pi,qk, so dpi,qk−1pi,qk,pj,qm−1=dpi,qk−1,pj,qm−1. This shows that(2)dg,pj,qm−1=dpi,qk−1,pj,qm−1+1,=dpi,qk−1pi,qk,pk,qm−1+1
This implies thatdg,pj,qm−1≠dh,pj,qm−1. Now, if g=pi,qk−1 and h=pi,qk−1pi,qk, then as pi,qk is nearer to pi,qm−1 as compared to pi,qk−1 (pi, qk−1), so dpi,qk−1pi,qk,pi,qm−1=dpi,qk,pi,qm−1. This shows that(3)dg,pi,qm−1=dpi,qk,pi,qm−1+1=dpi,qk−1pi,qk,pi,qm−1+1
This further shows thatdg,pi,qm−1≠dh,pi,qm−1. Thus, every pair g,h∈X is resolved by M.Case 2.
Letg,h∈Q. Since S is the mixed resolving set of Q, there exists s=wi,o∈S, such that(4)dg,s≠h,s.
Consider the pendant vertexwi,qm−1∈S∗. Then, any path from g (respectively h) to wi,qm−1 must contain s=wi,o and(5)dg,wi,qm−1=dg,wi,o+m–1,dh,wi,qm−1=dh,wi,o+m–1.
Asdg,s≠h,s, so dh,wi,qm−1≠dg,wi,qm−1. Thus, all elements of Q are resolved by M.Case 3.
Last, letg∈Q, h∈X. Then, h=pi,qj or h=pi,qj−1pi,qj. In any case, dg,pi,qm−1≥m–1 but dh,pi,qm−1≤m–2, which shows that the pair g,h in this case are also resolved by M. Hence, M is a mixed metric generator and dimmQ′=n.
Now, we note that by consideringo as the pendant vertex of P2, the corona graph Q′=QoK1 is actually the rooted product graph of Q by P2, i.e., QoK1=Q⊳OP2.
As a consequence, the following corollary can be stated.Corollary 2.
IfQ′ is a corona graph with t vertices, then dimmQ′=t/2.


## 3. Mixed Fault-Tolerant Generators of Graphs

A mixed metric generatorMf of a graph J is termed as the mixed fault-tolerant (MFTM) generator, if for u∈Mf,Mf∖u, u is also a mixed generator. The smallest MFTM generator is termed as MFTM basis, and its cardinality is MFTM dimension dimmfJ.Remark 1.
From definition, it is obvious that the MFTM dimension is always greater than or equal to the mixed metric dimension, i.e., for any graphJ,(6)dimmfJ≥dimmJ+1.Example 1.
TakeP3□P3 with labeling as shown in Figure 1 and M=v1,v3,v7,v9⊆VP3□P3. Then, the distance coordinate vectors of all vertices of P3□P3 relative to M are computed as follows:(7)rv1|M=0,2,2,4,rv2|M=1,1,3,3,rv3|M=2,0,4,2,rv4|M=1,3,1,3,rv5|M=2,2,2,2,rv6|M=3,1,3,1,rv7|M=2,4,0,2,rv8|M=3,3,1,1,rv9|M=4,2,2,0.
Similarly, the distance coordinate vectors of all of its edges relative toM are computed as follows:(8)re1|M=0,1,2,3,re2|M=1,0,3,2,re3|M=1,2,1,2,re4|M=2,1,2,1,re5|M=2,3,0,1,re6|M=3,2,1,0,re7|M=0,2,1,3,re8|M=1,3,0,2,re9|M=1,1,2,2,re10|M=2,2,1,1,re11|M=2,0,3,1,re12|M=3,1,2,0.
We can see that all distance coordinate vectors are distinguished by at least two points. Thus,M is a MFTM generator, and dimmfP3□P3≤4. But from Proposition 4.4 of [10], dimmP3□P3=3. This along with [7] implies that dimmfP3□P3≥4. Thus, we have dimmfP3□P3=4.
To recall, for the vertexz in a graph J, the open neighbourhood Nz is the collection of all vertices adjacent to z and closed neighbourhood is Nz=Nz∪z. For a vertex w, a vertex q∈Nw is referred to as maximal neighbourhood of w if Nw⊆Nq. A vertex v is referred to as the dominant vertex if it is adjacent to all other vertices of graph.Figure 1
GraphP3□P3.Lemma 1.
(see [10]). Consider u∈VJ and M=VJ∖u. Suppose for each w∈Nu, there is y∈S, such that dvw,x≠dw,y. Then, M is a mixed metric generator for J.Lemma 2.
(See [6]). For a graph J, let S be a metric generator and Ty=w∈VJ:Ny⊆Nw for ∈S. Then, Sf=∪y∈SNy∪Ty is a FTM generator.Theorem 2.
A connected graph of order at least 3 contains a mixed fault-tolerant (MFTM) generator if and only every vertex is neither a pendant vertex nor possesses a maximal neighbourhood.Proof.
LetM=q1,q2,…,qs be a MFTM generator of connected graph J. Suppose p2 is a pendant vertex of J. Then, there is a unique pendant edge with one end vertex as p1, say p=p1p2 . Then, p2∈M by Corollary 1, i.e., p2=qj for some j=1,…,s. Now, assume that the distance coordinate vector of p1 relative to M is given as(9)rp1|M=d1,d2,…,dj−1,1,dj+1,…,ds.
Asp1 is adjacent to p2 and p2=qj, therefore jth coordinate of rp1|M is equal to 1. Since p2 is a pendant vertex, every path from any vertex of J to p2 must contain vertex p1. This implies that p1 is nearer to any vertex of J than p2. This further implies that for p2≠y∈VJ∪EJ, we have dy,p=dy,p1 but dp2,p. Thus, the distance coordinate vector of edge p relative to M is given as(10)rp|M=d1,d2,…,dj−1,0,dj+1,…,ds.
Thejth coordinate is 0 because p=p1p2 and p2=qj. It is cleared from [3, 11] that the coordinate vectors of p1 and p differ exactly by one coordinate. This further implies that rp1|M∖p2=rp|M∖p2. This shows that M cannot be a MFTM generator, which leads to a contradiction. Next, we may assume that the graph J has no pendant vertex, but there exists a vertex t having maximal neighbourhood c, i.e., Nt⊆Nc. This implies that dc,t=1 but dtc,t=0. The elements tc and c can only be distinguished by the vertex t because if there is a vertex m∈M, such that m≠t and dc,m≠dm,tc, then as dm,tc=mindt,m,dc,m, so(11)dt,m<dc,m.
This further implies that any shortest path fromm to t must have a vertex from Nt different from c. As degt≥2, there is a vertex t1∈Nt∖c on the shortest path from m to t. Since Nt⊆Nc, c ∼ t1. Therefore,(12)dm,c≤dm,t1+dt1,c=1+dm,t1=dm,t.
This contradicts (6). Thus, tc and c can only be distinguished by t. Now, if ∉M, then M cannot be a mixed generator. On the other hand, if t∈M, then M∖t cannot not be the mixed generator. In any case, M is not a MFTM generator which again leads to a contradiction. Conversely, suppose that any vertex of J is the nonpendant vertex and does not have any maximal neighbourhood, i.e., for a∈VJ,dega≥2 and Na⊈Ny for any y∈Na. For any a∈VJ, we exhibit that the set VJ\a is a mixed generator. Let b∈Na. As dega≥2 and Na⊈Nb (by assumption), there is a vertex a1 (different from a and b), such that a1∼a but a1≁b. Then, da1,b>1 but da1,a=1. This shows that da1,ab=da1,a≠da1,b. Using Lemma 1, it is easy to see that VJ\a is a mixed generator for any a∈VJ. Thus, the vertex set VJ itself is the MFTM generator.Corollary 3.
A tree does not possess the mixed fault-tolerant generator.Proof.
Since a tree must have minimum two pendant vertices, the result follows using Theorem2.Corollary 4.
A connected graph containing a dominant vertexd have no mixed fault-tolerant generator.Proof.
Letd be a dominant vertex of connected graph J. Then, d serves as maximal neighbourhood of every vertex of VJ\d. The result follows by using Theorem 2.Theorem 3.
SupposeJ is a graph having girth at least four and contains the MFTM generator. If M is a mixed basis of graph J, then Mf=∪m∈MNm∪∩mi∈NmNmi is a MFTM generator for J.Proof.
Supposea∈VJ. If a∉M, then as M⊆Mf\a, so Mf\a is a mixed generator. Thus, we may assume that a∈M. Now, we show that Mf\a still is a mixed generator for J. For this, take two elements g,h∈VJ∪EJ. Now, there arise the following cases:Case (1): supposeg,h∈VJ, such that g≠h. As g and h both are vertices, so using Lemma 1, these can be distinguished by a vertex of Sf\a, where Sf=∪m∈MNm∪Tm and Tm:=m1∈VJ:Nm⊆Nm1. To show g and h are distinguished by some element of Mf\a, it is enough to exhibit that Sf⊆Mf. To show this, take a′∈Tm⊆Sf. Then, clearly, Nm⊆Na′, that is for every b′∈Nm,a′∼b′. This implies that a′∈Nb′ for every b′∼m or we can say that a′∈∩b′∈NmNb′⊆Mf.Case (2): now supposeg and h are the two distinct edges, such that g=g1g2 and h=h1h2. Clearly, one of gi must be different from one of hj. Suppose there does not exist any vertex in Mf\a that distinguished these edges. Then, as M is mixed metric and M⊆Mf, so the edges g and h must be distinguished by the vertex a, that is, da,g≠da,hd(a, g). Assume without any loss of generality (WLG) that(13)da,g<da,h.Now, there are two possibilities, either all vertices on these edges are distinct or there is some common vertex between them.Case 2(a): supposeg1,g2,h1, and h2 are distinct, i.e., edges are nonadjacent. Using (13), we have(14)da,g≤da,h−1,minda,g1,da,g2≤minda,h1,da,h2−1.Assume WLG thatg1 and h2 are nearer to the vertex a relative to g2 and h1, respectively. Then, from (14), we have(15)da,g1≤da,h2−1.Now assume thatg1≠a and a′∈Na lies on the minimum path between a and g1. Then, clearly, a′∈Mf\a ∈ Fm \ {a} being member of neighbourhood of a, we can write(16)da,g1=1+da′,g1By using (15) and (16), we have(17)da′,g1+1≤da,h2−1Now, by taking the patha−a′−⋯−h2, we have da′,h2+1≥da,h2. Then, using (17), we have(18)da′,g1+1≤da,h2−1≤da′,h2,da′,g1≤da′,h2−1,da′,g1<da′,h2.Sincea′∈Na and lies on the minimum path between g1 and a and da,g1<da,g2, therefore da′,g1<da,g1<da,g2. Now, by taking the path a−a′−⋯−g2, we have da′,g1<da,g2≤da′,g2+1. This implies that da′,g1≤da′,g2. Thus, we can write(19)da′,g=minda′,g1,da′,g2=da′,g1.Also, we have(20)da′,h=minda′,h2,da′,h1.We claim thatda′,g1<da′,h1, for otherwise, da,g1=1+da′,g1≥1+dh1,a′≥da,h1≥da,h2 which contradicts [10]. Hence, da′,g1<da′,h2, and using [1, 4, 13], we can write(21)da′,g=da′,g1<minda′,h2,da′,h1=da′,h,Which implies that edgesg and h are distinguished by a′∈Mf\a.Now, ifa coincides with g1, then g2∈Mf\a, such that dg,g2=0 and dh,g2≥1. Hence, g and h are distinguished by g2.Case 2(b): now suppose thatg and h are adjacent and g2 is their common vertex, i.e., g=g1g2 and h=g2h1. Furthermore, suppose that a and g1 are distinct. This implies that a≠g1,g2,h1 and dg1,a<dg2,a. Then, (13) becomes(22)da,g1<minda,g2,da,h1.Ifa′∈Na lies on the minimum path between a and g1, then we have(23)da′,g=dg1,a′<dg2,a′.Also, we have(24)da′,h=mindg2,a′,dh1,a′.We claim thatda′,g1<da′,h1; for otherwise, we have(25)da,g1=1+da,g2≥1+da′,h1≥da,h1.This contradicts (22). Thus, da′,g1<da′,h1, and using (23) and (24), we can write(26)da′,g=dg1,a′<mindg2,a′,dh1,a′=da′,h.Thus, the edges are distinguished bya′∈Mf\a. Now, suppose a lies on one of the edges g and h. Using (13), it is easy to see that only possibility is that the vertex a coincides with vertex g1. If the vertex h1∈Mf\a, then g and h are distinguished by h1. Thus, we may suppose that h1∉Mf=Nm∪∩mi∈NmNmi. This further implies that there exists a vertex a′∈Na, such that h1≁a′. If g2∼a′, then we have a triangle g1−a′−g2−g1, which is not possible as the graph J has girth at least four. Thus, g2≁a′ which implies that da′,h≥2, but da′,g=1. Hence, this case is completed.Case (3): finally, suppose thatg is a vertex and h=h1h2 is an edge of J, such that there does not exist any vertex in Mf\a that distinguishes them. Then, g and h can only be distinguished by a, i.e., da,g≠da,h. Now, the vertex g may lie on h or not.Case 3a: supposeg≠h1,h2 and a is distinct from g, h1, and h2. Furthermore, suppose(27)dg,a<dh,a.If the vertexa is nearer to h1 as compared to h2, then from (27), we have(28)dg,a≤dh1,a–1.Considera′∈Na on the minimum path between a and g. Then, dg,a′=dg,a−1, and from (28), we have (29)dg,a′+1≤dh1,a–1.From the patha−a′−⋯−h1, we can see that(30)da,h1≤da′,h1+1.Now, using (29) and (30),(31)dg,a′+1≤da′,h1,dg,a′<da′,h1.(32)da′,h=minda′,h1,da′,h2.We claim thatda′,g<da′,h2; for otherwise, da,g=1+da′,g≥1+da′,h2≥da,h2, that is, da,g≥da,h2≥da,h, which contradicts (27). Thus,(33)da′,g<da′,h2.Using (31), (32), and (33), we can write(34)da′,g<minda′,g1,da′,h2=da′,h.This implies that the vertexg and edge h are distinguished by a′∈Mf\a. The case da,g>da,h can be dealt using same arguments. Now, suppose that a = g. If h1 or h2∈Mf, then g and h are distinguished by h1 (or h2). Therefore, we may suppose that h1,h2∉Mf and dh1,a≤dh2,a. Then, there exists a'′∈Na, such that h1≁a'′. By using the paths a−a'′−⋯−h2 and a−a'′−⋯−h1, we can see that(35)da′,h2≥da,h2−1≥da,h1−1≥1+da′,h1−1=dh1,a′≥2.Sincea = g and a″∼a, so dg,a′=1, i.e., a′∈Mf\a resolves g and h. Now, assume that vertex a coincides with some vertex of h, say h1, i.e., h=h1h2=ah2. If g∈Mf, then g and h are distinguished by g. But if g∉, then g is not adjacent to some vertex b′∈Na. This implies that db′,h=1 and db′,g≥2. This completes this subcase.Case 3b: suppose that the vertexg lies on h. Let h1=g. If a≠g,h2, then we have(36)dh,a=dh2,a<dg,a≤dh2,a+1.Thus,(37)da,g=da,h2+1.Ifh2,∈Mf, then g and h are distinguished by h2, but if h2,∉Mf, then h2,≁a. This implies that there exists a vertex b'′∈Na on the minimum path between a and h2. Using (37), we have(38)db′,g=da,h2=1+db′,h2.This implies thatdb′,g>db′,h2. Hence, g and h are distinguished by b'′∈Mf\a. Finally, suppose that the vertices a and g both are on the edge h, that is, h=ag. As the graph J possesses the MFTM generator, so by Theorem 2, the vertex a is not a pendant vertex and therefore dega>1. This further implies that there exists a vertex c∈Na⊆Mf\a other than g, i.e., c≠g. As J has girth at least four, so c is not adjacent to g ,and we have dc,h=1, whereas dc,g≥2. Thus, in all cases, any pair of element of J is distinguished by vertices of Mf\a. This completes the proof.


## 4. Conclusion

In this study, it is shown that the mixed metric dimension for the rooted product of graph of ordern≥2n by path graph by taking pendant vertex as root vertex is n. As a consequence, it is presented that the mixed metric dimension of the corona graph with t vertices is t/2. The notion of the mixed fault-tolerant metric generator is defined for the mixed generator. As the graphs like path graph, tree, and complete graph do not have any mixed metric generators, so it is important to classify those graphs which possess the mixed generator. This problem is settled in this study, and the graphs having the mixed fault-tolerant metric generator are characterized. Specifically, it is shown that the necessary and sufficient conditions for existence of the mixed generator for a graph Q are that the graph Q does not have pendant vertices and does not contain any vertex having maximal neighbourhood. Moreover, the mixed fault-tolerant metric resolving set for a graph Q with girth at least 4 is presented as Fm=∪t∈ANt∪∩ti∈NtNti, where Nt and Nt are the closed and open neighbourhoods, respectively, and A is the mixed basis for Q.



---

*Source: 9773089-2022-05-28.xml*