# On Fault-Tolerant Resolving Sets of Some Families of Ladder Networks

Authors: Hua Wang; Muhammad Azeem; Muhammad Faisal Nadeem; Ata Ur-Rehman; Adnan Aslam
Journal: Complexity
 (2021)

---

## Abstract

In computer networks, vertices represent hosts or servers, and edges represent as the connecting medium between them. In localization, some special vertices (resolving sets) are selected to locate the position of all vertices in a computer network. If an arbitrary vertex stopped working and selected vertices still remain the resolving set, then the chosen set is called as the fault-tolerant resolving set. The least number of vertices in such resolving sets is called the fault-tolerant metric dimension of the network. Because of the variety of applications of the metric dimension in different areas of sciences, many generalizations were proposed, and fault tolerant is one of them. In this paper, we computed the fault-tolerant metric dimension of triangular snake, ladder, Mobius ladder, and hexagonal ladder networks. It is important to observe that, in all these classes of networks, the fault-tolerant metric dimension and metric dimension differ by 1.


---

## Body

## 1. Introduction

LetG=VG,EG be a simple connected graph, where VG and EG are the set of vertices and edges, respectively. The distance du1,u2 between a pair of vertices u1,u2∈VG is the length of the shortest path joining them. A vertex u resolves or distinguishes a pair u1,u2 if du1,u≠du2,u. The representation of an arbitrary vertex u corresponding to an ordered nonempty subset of vertices Q=q1,q2,…,qh⊂VG is the h-component vector ru|Q=du,q1,du,q2,…,du,qh. A subset Q⊂VG is named the resolving set if any pair u1,u2∈VG possesses the condition of unique representation, that is, ru1|Q≠ru2|Q. The least possible cardinality of Q is named the metric dimension of the graph G and symbolized as dimG. A resolving set containing a least possible number of elements is named as basis. A basis set Qf of G is called the fault-tolerant basis set if, for every u∈Qf, the subset Qf/u again resolves the vertices of G. The least number of vertices in Qf is termed as the fault-tolerant metric dimension of G and is denoted by dimfG. Chaudhry et al. [1] proved an important relationship between the fault-tolerant metric dimension and the metric dimension of a graph G.(1)dimfG≥dimG+1.First time, the idea of metric dimension was studied by Slater [2] in 1975 and later by Harary and Melter [3] in 1976. Chartrand et al. [4] considered metric bases as sensors. If any of the sensors did not operate correctly, then we do not have sufficient knowledge to deal with the intruders. Hernando et al. [5] presented the idea of fault-tolerant metric dimension to overcome this kind of problems. Fault-tolerant basis set delivers accurate information despite being one of the sensors is not working. Because of different applications, the study of fault-tolerant resolving sets of different networks is as sundry as the study of the metric dimension is.It was proved that computing the metric dimension is NP-complete [6]. However, the idea of uniquely identifying every vertex in a graph based on distance is very useful. The application of this concept in chemical structures was presented by Chartrand el al. [4]. In robot navigation, the work by Khuller et al. [7] motivated the researchers for the theoretical investigation of the metric dimension. The resolving set has found a number of applications. For more details, see [8–10]. Generally, computing the fault-tolerant metric dimension is also an NP-complete problem. Computing the fault-tolerant metric dimension is considered as one of the interesting but difficult problems in combinatorics. So far, only few structures have been investigated. In the initial paper, Hernando et al. [5] computed the fault-tolerant basis sets of tree T. For a graph G, they derived a connection between the fault-tolerant metric dimension and the metric dimension, that is, dimfG≤dimG1+2×5dimG−1. Javaid et al. [11] studied this parameter of cycle graph Cn and discussed some bounds on the partition dimension. For more results related to the fault-tolerant metric dimension, the interested readers can see [12–23].The core objective of this paper is to find some classes of graphs satisfying the equationdimG=dimfG+1. It has been observed that if G is ladder Lm,m≥3, Möbius ladder MLm,m≥4, and hexagonal Möbius ladder graph HMLm,m≥2, then the metric dimension and fault-tolerant metric dimension differ by 1. Also, for triangular snake graph TSn, the above equality holds if and only if n=5,7. In order to prove these results, we need some results from the literature.Theorem 1.
(see [4]). The metric dimension of a graph is 1 iff G≅Pn.Theorem 2.
(see [24]). Let MLm be a Möbius ladder graph. Then,(2)dimMLm=3ifm≥4even,4ifm≥5odd.Theorem 3.
(see [25]). Let HMLm be a hexagonal Möbius ladder graph. Then,(3)dimHMLm=2ifm=2,3ifm≥3.Theorem 4.
(see [5]). Let Ln be a ladder graph with n≥3. Then,(4)dimLn=2.


## 2. Fault-Tolerant Metric Dimension of the Triangular Snake Graph

This section deals with the metric dimension and fault-tolerant metric dimension of the triangular snake graph. LetPn be a path with vertex set VPn=v1,v2,…,vn, where n=2s+1 is an odd integer. A triangular snake graph TSn is constructed from Pn by connecting v2i−1 with v2i+1 for 1≤i≤s. Note that s represents the cardinality of triangles in TSn. The triangular snake graph is depicted in Figure 1. In the following Lemma 1, we calculate the metric dimension dimTSn of triangular snake graph TSn.Figure 1
Triangular snake graphTSn.Lemma 1.
LetTSn be a triangular snake graph with s≥2. Then,(5)dimTSn=2.Proof.
From Theorem1, it follows that dimTSn≥2. To prove that dimTSn=2, we prove that dimTSn≤2. Let Q=v1,vn be a resolving set. Then, the representations of vertices vt regarding the resolving set Q are as follows:(6)rvt|Q=t−12,2s−t−12ift=1,3,5,…,2s−1,t2,2s−t+22ift=2,4,6,…,2s−2,t2,1ift=2s,t2,0ift=2s+1.
As all the vertices have unique representations regarding the resolving setQ, hence, dimTSn≤2.Theorem 5.
LetTSn be a triangular snake graph; then,(7)dimfTSn=3ifs=2,3,4ifs≥4.Proof.
First, we show thatdimfTSn=3 when s=2,3. To prove this, it is enough to show that dimfTSn≤3. The inequality dimfTSn≥3 follows from Lemma 1 and equation (1). If we take Qf=v1,v4,v2s+1, then it satisfies the condition of the fault-tolerant resolving set. The following is the representation of any vertex vt of the graph TSn with respect to Qf:(8)rvt|Qf=t2,24−t2+z,2s+1−t2,where z=1 when t=3,5 and zero, otherwise.
Now, we prove thatdimfTSn≤4 when s≥4. For this, we construct a fault-tolerant resolving set. Take Qf=v1,v2,v2s−2,v2s; the following is the representation of any vertex of graph with Qf:(9)rvt|Qf=t−12,t−22+z,2s−2−t2+z,2s−t2+z,where z=1 for t=even and zero, otherwise. Hence, it follows from the above discussion that dimfTSn≤4 since every vertex of TSn has a unique representation regarding resolving set Qf.
We prove the reverse inequalitydimfTSn≥4 by the contradiction method. Suppose dimfTSn<4, it follows from Lemma 1 that dimfTSn=3. Let us consider some resolving set Qf with cardinality 3.Case 1.
LetQf=v1+l,v2+l,v3+l, where l≡0mod3. If we choose Qf=v1,v2,v3, then rv4|Qf=rv5|Qf. For any other choice of Qf, we get rv1|Qf=rv2|Qf.Case 2.
LetQf=vi,v1+l,v2+l or Qf=vi,v1+l,v3+l, where 1≤i≤2 and l≥3. In other words, we are taking the first vertex from the first triangle and the remaining vertices from any arbitrary triangle. Then, it is easy to observe that there exists an integer 6≤j≤n−1 such that rvj|Qf=rvj+1|Qf.Case 3.
LetQf=vi,vj,vk, where 1≤i,j,k≤n. Then, rv1|Qf=rv2|Qf.
Hence, it follows from the above discussion thatdimfTSn≠3 when s≥4. This implies that dimfTSn≥4 when s≥4. This completes the proof.


## 3. Fault-Tolerant Metric Dimension of Ladder Graphs

A ladder graph is obtained by the Cartesian product of pathPn with path P2 and is denoted by Lm. Observe that m=2n. The ladder graph is shown in Figure 2. In the following theorem, we compute the fault-tolerant metric dimension of the ladder graph.Figure 2
Ladder graphLm.Theorem 6.
LetLm be a ladder graph with m≥3. Then,(10)dimfLm=3.Proof.
The inequalitydimfLm≥3 follows from Theorem 4 and equation (1). To prove dimfLm≤3, we construct a fault-tolerant resolving set. Let Qf=v1,v3,v2n−1; then, the representation of any vertex vt of the graph with Qf can be computed as(11)rvt|Qf=t−12,t−32+w,2n−1−t2+z,where w=1 for t=2 and z=1 for t=even and zero, otherwise. Observe that all the vertices of Lm have a unique representation regarding fault-tolerant set Qf. Hence, dimfLm=3.
The Möbius ladder was first introduced by Richard Guy and Frank Harary [26]. It is a three-regular graph created by a cycle Cn by joining vertices u,v of the cycle iff du,v=diamCn. Möbius ladder has an even number of vertices. It is denoted by Mn, where n=2m. The vertices which satisfy this condition are called antipodal. The graph of the Möbius ladder is shown in Figure 3. Möbius ladders have several uses in different fields of sciences such as stereochemistry, computer networks, and electrotechnology. In the next result, we find the fault-tolerant metric dimension of the Möbius ladder.Figure 3
Möbius ladder graphMn.Theorem 7.
LetMn be a Möbius ladder graph. Then,(12)dimfMn=4ifm≥4andm=even,5ifm≥5andm=odd.Proof.
Letm≥4 be an even integer. The inequality dimfMn≥4 follows from Theorem 2 and equation (1). To prove dimfMn≤4, we construct a set satisfying the definition of fault-tolerant metric dimension. Let Qf=v1,v2,vm,vm+1; then, the distances of any vertex vt of the graph corresponding to Qf can be computed as follows.
Distance of vertexvt from vertex v1 is(13)dvt,v1=t−1ift=1,2,…,m+22,m−t+2ift=m+22+1,…,m+1,t−mift=m+2,…,m+22,2m−t+1ift=m+22+1,…,2m.
Distance of vertexvt from vertex v2 is(14)dvt,v2=t−2ift=1,2,…,m+42,m−t+3ift=m+22+1,…,m+1,t−m−1ift=m+2,…,3m2+1,2m−t+2ift=3m2+2,…,2m.
Distance of vertexvt from vertex vm is(15)dvt,vm=m−tift=m2,m2+1,…,m+1,t+1ift=1,2,…,m2−1,t−mift=m+2,…,3m2,2m−t+1ift=3m2+1,…,2m.
Distance of vertexvt from vertex vm+1 is(16)dvt,vm+1=tift=1,2,…,m+12,m−t+1ift=m+12+1,…,m+1,t−m−1ift=m+2,…,3m2+1,2m−t+2ift=3m2+2,…,2m.
Since all the vertices ofMn have unique representations regarding the resolving set Qf, hence, dimfMn=4.
Now, letm≥5 be an odd integer. To prove that dimfMn=5, we construct a resolving set satisfying the condition of the fault-tolerant metric dimension. Let Qf=v1,v2,vm+5/2,vm+2,v3m+5/2; then, the distance of any vertices vt from the vertex vm+5/2,vm+2, and v3m+5/2 is as follows.
Distance of vertexvt from vertex vm+5/2 is(17)dvt,vm+5/2=m−32+tift=1,2,3−t+m−12ift=3,4,…,m+1,t−m+52ift=m+2,m+3,t−3m+52+1ift=m+4,…,2m.
Distance of vertexvt from vertex vm+2 is(18)dvt,vm+2=t−2+1ift=1,2,…,m+12,m−t+2ift=m+32,…,m+1,t−m−2ift=m+2,m+3,…,3m+12,3−t+2mift=3m+52,…,2m.
Distance of vertexvt from vertex v3m+5/2 is(19)dvt,v3m+5/2=m−52+tift=1,23,m+52−t+1ift=4,…,m+1,t+3m+52ift=m+2,m+3,…,2m.
Since all the vertices ofMn have unique representations regarding decided resolving set Qf, hence, dimfMn=5.
A hexagonal Möbius ladderHMLm,n is constructed by subdividing each horizontal edge of the square lattice; thus, we obtained a lattice in which each cycle has order six; after creating this lattice, twist the recently attained lattice 180° and join the utmost left and right vertices as shown in Figure 4. Hexagonal Möbius ladder HMLm,n contains m horizontal and n vertical cycles. Let HMLm=HMLm,1 be a hexagonal Möbius ladder with m horizontal cycles and 1 vertical cycle. In the next theorem, we compute the fault-tolerant metric dimension of HMLm.Figure 4
Hexagonal Möbius ladder graphHMLm.Theorem 8.
LetHMLm be a hexagonal Möbius ladder graph. Then,(20)dimfHMLm=3ifm=2,4ifm≥3.Proof.
Letm=2; the inequality dimfHMLm≥3 follows from Theorem 3 and equation (1). To prove dimfHMLm≤3, we construct a set satisfying the definition of fault-tolerant metric dimension. Let Qf=v1,v4,v6; then, the distances of any vertex vt of the graph corresponding to Qf can be computed as follows.
Distance of vertexvt from vertex v1 is(21)dvt,v1=1ift=2,5,8,2ift=3,4,6,7.
Distance of vertexvt from vertex v4 is(22)dvt,v4=1ift=3,5,2ift=1,2,6,7,3ift=8.
Distance of vertexvt from vertex v6 is(23)dvt,v6=1ift=5,7,2ift=1,3,4,8,3ift=2.
It is easy to see that every vertex ofHMLm has its unique representation with the resolving set Qf. Hence, dimfHMLm=2.
Letm≥3; to prove that dimfHMLm=4, it is enough to construct a fault-tolerant resolving set of four elements that satisfy the condition of fault-tolerant metric dimension. Let Qf=v1,v2,v2m,v2m+2; then, the distance of any vertex vt of HMLm with Qf can be computed as follows.
Distance of vertexvt from vertex v1 is(24)dvt,v1=t−1ift=1,2,…,m+1,2m−t+2ift=m+2,…,2m+1,t−2mift=2m+2,…,3m,4m−t+1ift=3m+1,…,4m.
Distance of vertexvt from vertex v2 is(25)dvt,v2=t−2ift=1,2,…,m+2,2m−t+3ift=m+3,…,2m+1,t−2m−1ift=2m+3,…,3m+1,t−2m+1ift=2m+2,4m−t+2ift=3m+2,…,4m.
Distance of vertexvt from vertex v2m is(26)dvt,v2m=t+1ift=1,2,…,m−1,2m−tift=m,…,2m+1,t−2mift=2m+2,…,3m,4m−t+1ift=3m+1,…,4m.
Distance of vertexvt from vertex v2m+2 is(27)dvt,v2m+2=t−2+1ift=1,3,4,5,…,2m+12,3ift=2,2m−t+2ift=2m+12+1,…,2m+1,t−2m−2ift=2m+2,2m+3,…,6m+32,3−t+4mift=6m+32+1,…,4m.
It is easy to see that all the vertices ofHMLm have unique representations regarding resolving set Qf. Hence, dimfHMLm=3.


## 4. Conclusion

In this article, we study the fault-tolerant metric dimension of the triangular snake graph, ladder, Möbius ladder, and hexagonal Möbius ladder. It is known that, for cycle graphCn, we have dimfCn=dimCn+1. Therefore, it is interesting to find some classes of graph in which this equality holds. Note that, in case of the triangular snake graph, ladder, Möbius ladder, and hexagonal Möbius ladder, we have dimf=dim+1.



---

*Source: 9939559-2021-05-17.xml*