# Fault-Tolerant Resolvability in Some Classes of Line Graphs

Authors: Xuan Guo; Muhammad Faheem; Zohaib Zahid; Waqas Nazeer; Jingjng Li
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Fault tolerance is the characteristic of a system that permits it to carry on its intended operations in case of the failure of one of its units. Such a system is known as the fault-tolerant self-stable system. In graph theory, if we remove any vertex in a resolving set, then the resulting set is also a resolving set, called the fault-tolerant resolving set, and its minimum cardinality is called the fault-tolerant metric dimension. In this paper, we determine the fault-tolerant resolvability in line graphs. As a main result, we computed the fault-tolerant metric dimension of line graphs of necklace and prism graphs (2010 Mathematics Subject Classification: 05C78).


---

## Body

## 1. Introduction and Preliminaries

LetG be a simple connected graph with vertex set VG and edge set EG. The distance ds,t between two vertices s,t∈VG is the length of a shortest path between them. The degree of a vertex s is the number of edges that are incident to it. Let W=w1,w2,…,wl⊂VG be an ordered set and s∈VG; then, the representation rsW of s with respect to W is the l-tuple ds,w1,ds,w2,…,ds,wl. W is called a resolving set if different vertices of G have different representations with respect to W. A resolving set with a minimum number of elements is called a basis for G, and the cardinality of the basis is known as the metric dimension of G, represented by βG. For W=w1,w2,…,wl⊂VG, the ith component of rsW is 0 if and only if s=wi. Hence, to prove that W is a resolving set, it is enough to show that rsW≠rtW for each pair s≠t∈VG/W. The absolute difference representation of s,t∈VG with respect to W is ADs,tW=dGs,w1−dGt,w1,…,dGs,wl−dGt,wl. So, W is a resolving set if ADs,tW has at least one entry in the l-vector different from zero for s≠t∈VG.The concept of metric dimension of the general metric space was presented in 1953 (see [1]). After twenty years, the concept of resolving set in graphs was first introduced by Slater [2, 3] in 1975 and also independently by Harary and Melter [4] in 1976. The resolving sets were basically defined to determine the location of the intruder in a network, but later, Chartrand and Zhang used metric bases in the fields of robotics, chemistry, and biology in 2003, see [5, 6].It will be a difficult task to locate an interrupter if one of the sensors does not function in a proper way. In order to tackle such problems, Hernando et al. [7] gave the idea of the fault-tolerant resolving set. Fault-tolerant resolving set is a resolving set if the removal of any element keeps it resolving. Formally, a resolving set W′ of any graph G is called a fault-tolerant resolving set if W′/w for all w∈W′ is also a resolving set of G. The minimum cardinality of the fault-tolerant resolving set is called the fault-tolerant metric dimension, and it is denoted by β′G. In other words, for all s,t∈VG, ADs,tW′ has at least two entries in the l-vector different from zero.Fault-tolerant metric dimension is an interesting concept and has been studied by many authors. For instance, Hernando et al. in [7] computed the fault-tolerant resolving set for tree graphs and proved that β′Pn=2 for the path graph Pn on n≥2 vertices. Voronov in [8] computed the fault-tolerant metric dimension of the king’s graph. Recently, Hussain et al. in [9] computed closed formulas for the fault-tolerant metric dimension of wheel-related graphs. Raza et al. in [10] computed the fault-tolerant metric dimension of some classes of convex polytopes. Raza et al. in [11] showed that the fault-tolerant metric dimension of the complete graph on n vertices is n. Javaid et al. in [12] proved that β′Cn=3 for the cycle graph Cn on n≥3 vertices. For more details on the fault-tolerant metric dimension, see [13–15].The line graphLG of graph G is the graph whose vertices are the edges of G, and two vertices e and f of LG are connected if and only if they have a common end vertex in G. The metric dimension of line graphs is studied in [6, 10, 16–18]. For more details, see [19–21]. Here, we determine the fault-tolerant metric dimension in line graphs. The fault-tolerant metric dimension in line graphs is only known for path and cycle graphs as given in the following theorem.Theorem 1.
The fault-tolerant metric dimension of the line graphs of path and cycle graphs of ordern is 2 and 3, respectively.Proof.
The results are obvious from the definition of the line graph, and the results are proved in [7, 12], respectively. Since it is difficult to compute the exact values of β′G for every graph G, A. Estrado-Moreno et al. gave some of the important bounds on the fault-tolerant metric dimension of graphs as follows.Lemma 1 (see [22]).
LetG be any graph; then, βG<β′G.Lemma 2 (see [22]).
IfG≠Pn, then β′G≥3 for all G.
In [23], Khuller et al. studied an important property of graphs with metric dimension 2 as follows.Lemma 3 (see [23]).
LetG be a graph with metric dimension 2, and let v1,v2⊂VG be a resolving set in G. Then, the degree of both v1 and v2 is at most 3.Consequently, similar argument works for the graphs with fault-tolerant metric dimension 3 are given in the following lemma.Lemma 4.
LetG be a graph with fault-tolerant metric dimension 3, and let v1,v2,v3⊂VG be a fault-tolerant resolving set in G. Then, the degree of each vertex v1, v2, and v3 is at most 3. The rest of the paper is structured as follows: in Section 2, we will compute the fault-tolerant metric dimension of the line graph of the necklace graph. In Section 3, we will compute the fault-tolerant metric dimension of the line graph of the prism graph.


## 2. The Fault-Tolerant Metric Dimension of the Line Graph of the Necklace Graph

The necklace graphNen for n≥2 consists of the edge set ENen=fi,gi,hi:1≤i≤n+1 as shown in Figure 1.Figure 1
The necklace graphNen.For the fault-tolerant metric dimension of the line graph of the necklace graph, we have to construct a line graphLNen of Nen with n≥2 (see Figure 2).Figure 2
The line graphLNen of a necklace graph.In the following theorem, the result for the metric dimension of the line graph of the necklace graph is given.Theorem 2 (see [17]).
The metric dimension of the line graph of the necklace graphLNen is 3 for n≥2. Now, we will compute the fault-tolerant metric dimension of the line graph of the necklace graph.Theorem 3.
The fault-tolerant metric dimension of the line graph of the necklace graph is 4 forn≥2.Proof.
To prove this theorem, consider the following cases.Case 1 (n is odd).
Letn≥3, and take W′=f1,fn+1/2,fn+1,hn+1/2⊆VLNen. Representation of vertices fi with respect to W′ is(1)rfiW′=i−1,n+12−i,i+1,n+32−i,if1≤i≤n−12,i−1,i−n+12,n+1−i,1,ifn+12≤i≤n+32,n+3−i,i−n+12,n+1−i,i−n+12,ifn+52≤i≤n+1.
Now, representation of verticesgi with respect to W′ is(2)rgiW′=i,n+32−i,i+1,n+32−i,if1≤i≤n−12,i,2,n+2−i,1,ifn+12≤i≤n+32,n+3−i,i−n−12,n+2−i,i−n+12,ifn+52≤i≤n+1.
Representation of verticeshi with respect to W′ is(3)rhiW′=i,n+12−i,i+2,n+32−i,if1≤i≤n−12,n+12,1,n+12,0,ifi=n+12,n+3−i,i−n−12,n+1−i,i−n−12,ifn+32≤i≤n,1,n+12,1,n+32,ifi=n+1.
It can be easily seen thatADs,tW′ has at least two entries in the 4-vector different from zero for any s,t∈VLNen. Hence, W′ is a fault-tolerant resolving set of LNen. So, by using Theorem 2 and Lemma 1, β′LNen=4 for every odd n.Case 2 (n is even).
Letn≥2, and take W′=fn+2/2,h1,hn+2/2,gn+2/2⊆VLNen. For n=2, it is easy to verify that all the representations are distinct.
Now, representation of verticesfi for n≥4 with respect to W′ is(4)rfiW′=n2,1,n+22,n+22,ifi=1,n+22−i,i−1,n+42−i,n+42−i,if2≤i≤n2,0,n2,1,2,ifi=n+22,1,n+22,1,2,ifi=n+42,i−n+22,n+4−i,i−n+22,i−n2,ifn+62≤i≤n+1..
Representation of verticesgi for n≥4 with respect to W′ is(5)rgiW′=n+22,1,n+22,n2,ifi=1,n+42−i,i−1,n+42−i,n+22−i,if2≤i≤n2,2,i−1,1,i−n+22,ifn+22≤i≤n+42,i−n2,n+4−i,i−n+22,i−n+22,ifn+62≤i≤n+1.
Representation of verticeshi for n≥4 with respect to W′ is(6)rhiW′=n2,0,n+22,n2,ifi=1,n+22−i,i,n+42−i,n+22−i,if2≤i≤n2,1,n+22,0,1,ifi=n+22,i−n2,n+4−i,i−n2,i−n2,ifn+42≤i≤n,n+22,2,n+22,n+22,ifi=n+1.
It can be easily seen thatADs,tW′ has at least two entries in the 4-vector different from zero for any s,t∈VLNen. Hence, W′ is a fault-tolerant resolving set of LNen. So, by using Theorem 2 and Lemma 1, β′LNen=4 for every even n.


## 3. The Fault-Tolerant Metric Dimension of the Line Graph of the Prism Graph

The prism graphYn is Cartesian product graph Cn×P2, where Cn is the cycle graph of order n and P2 is a path of order 2. The prism graph Yn consists of 4-sided faces and n-sided faces with edge set EYn=ei,fi,gi;1≤i≤n as shown in Figure 3. The line graph LYn of the prism graph consists of 3-sided faces, 4-sided faces, and n-sided faces as shown in Figure 4. For our purpose, we label the inner cycle vertices of LYn by ei:1≤i≤n, middle vertices by fi:1≤i≤n, and the outer cycle vertices by gi:1≤i≤n.Figure 3
Prism graphYn.Figure 4
The line graphLYn of a prism graph.In the following theorem, the result for the metric dimension of the line graph of the prism graph is presented.Theorem 4 (see [24]).
LetYn be the prism graph; then, the metric dimension of the line graph of the prism graph is 3 for n≥3. Now, in the following theorem, we will compute the fault-tolerant metric dimension of the line graph of the prism graph.Theorem 5.
LetYn be the prism graph; then, the fault-tolerant metric dimension of the line graph of the prism graph is 4 for n≥3.Proof.
To prove this theorem, consider the following cases.Case 1 (n is even).
Letn≥4, and take W′=e1,e2,en+2/2,en+4/2⊆VLYn. Representation of vertices ei with respect to W′ is(7)reiW′=0,1,n2,n−22,ifi=1,i−1,i−2,n+22−i,n+42−i,if2≤i≤n+22,n+1−i,n+2−i,i−n+22,i−n+42,ifn+42≤i≤n.
Representation of verticesfi with respect to W′ is(8)rfiW′=1,1,n2,n2,ifi=1,i,i−1,n+22−i,n+42−i,if2≤i≤n2,n2,n2,1,1,ifi=n+22,n+1−i,n+2−i,i−n2,i−n+22,ifn+42≤i≤n.
Representation of verticesgi when n=4 with respect to W′ is(9)rgiW′=2,2,4−i,1+i,if1≤i≤2,6−i,i−1,2,2,if3≤i≤4.
Representation of verticesgi when n≥6 with respect to W′ is(10)rgiW′=2,2,n+42−i,n−22+i,if1≤i≤2,i,i+1,n+42−i,n+62−i,if3≤i≤n2,n+2−i,i−1,2,2,ifn+22≤i≤n+42,n+2−i,n+3−i,i−n2,i−n+22,ifn+62≤i≤n.
It can be easily seen thatADs,tW′ has at least two entries in the 4-vector different from zero for any s,t∈VLYn. Hence, W′ is a fault-tolerant resolving set of LYn. So, by using Theorem 4 and Lemma 1, β′LYn=4 for every even n.Case 2 (n is odd).
Forn=3, take W′=e1,f1,f3,g1⊆VLY3. It is easy to check that W′ is a fault-tolerant resolving set. Let n≥5, and take W′=e1,e2,en+1/2,g2⊆VLYn. Representation of vertices ei with respect to W′ is(11)reiW′=i−1,2−i,n+12−i,2,if1≤i≤2,i−1,i−2,n+12−i,i−1,if3≤i≤n+12,n−12,n−12,1,n+12,ifi=n+32,n+1−i,n+2−i,i−n+12,n+3−i,ifn+52≤i≤n.
Representation of verticesfi with respect to W′ is(12)rfiW′=1,1,n−12,1,ifi=1,i,i−1,n+12−i,i−1,if2≤i≤n−12,n+12,n−12,1,n−12,ifi=n+12,n+1−i,n+2−i,i−n−12,n+2−i,ifn+32≤i≤n.
Representation of verticesgi when n=5 with respect to W′ is(13)rgiW′=2,2,4−i,2−i,if1≤i≤2,3,2,2,1,ifi=3,7−i,3,i−2,2,if4≤i≤5.
Representation of verticesgi when n≥7 with respect to W′ is(14)rgiW′=2,2,n+32−i,2−i,if1≤i≤2,i,i−1,n+32−i,i−2,if3≤i≤n−12,n+12,i−1,2,i−2,ifn+12≤i≤n+32,n+2−i,n+3−i,i−n−12,n+2−i,ifn+52≤i≤n.
It can be easily seen thatADs,tW′ has at least two entries in the 4-vector different from zero for any s,t∈VLYn. Hence, W′ is a fault-tolerant resolving set of LYn. So, by Theorem 4 and Lemma 1, β′LYn=4 for every odd n.


## 4. Conclusion

In this paper, we have studied for the first time the fault-tolerant metric dimension of the line graph of a graph. We have given the exact values of the fault-tolerant metric dimension of the line graphs of necklace and prism graphs and found these values are independent of the number of vertices of a graph. In future, we will compute the exact value of the fault-tolerant metric dimension of the line graph of the kayak paddle graph. We will also discuss the fault-tolerant resolvability in graphs by using other graph operations.



---

*Source: 1436872-2020-09-26.xml*