# On the FAULT-TOLERANT Resolvability in Line Graphs of Dragon and Kayak Paddles Graphs

Authors: Muhammad Faheem; Zohaib Zahid
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

Because of its wide range of applications, metric resolvability has been used in chemical structures, computer networks, and electrical circuits. It has been applied as a node (sensor) in an electric circuit. The electric circuit will not be able to flow current if one node (sensor) in that chain becomes faulty. The fault-tolerant selfstable circuit is a circuit that permits the current flow even if one of the nodes (sensors) becomes faulty. If the removal of any node from a resolving set (RS) of the circuit is still a RS, then the RS of the circuit is considered a fault-tolerant resolving set (FTRS) and the fault-tolerant metric dimension (FTMD) is its minimum cardinality. Even though the problem of finding the exact values of MD in line graphs seems to be even harder, the FTMD for the line graphs was first discussed by Guo et al. [13]. Ahmad et al. [5] determined the precise value of the MD for the line graph of the kayak paddle graph. We calculate the precise value of the FTMD for the line graph in this family of graphs. The FTMD is a more generalized invariant than the MD. We also consider the problem of obtaining a precise value for this parameter in the line graph of the dragon graph. It is concluded that these families have a constant FTMD.


---

## Body

## 1. Introduction and Preliminaries

Network topology is the graphical depiction of electric circuits. Because convoluted electric circuits (networks) are difficult to work on and study in their natural state, network topology is developed to make them simple and intelligible. Using this technique, any electric circuit (network) can be changed (moulded) into its corresponding graph; open circuits replace current sources, while short circuits replace passive parts and voltage sources. Short circuits are termed branches in network topology and edges in graph theory conceptualization, while open circuits are called nodes in network topology and vertices in pure mathematical graph theory. The following is the formal definition of a graphical depiction of an electric circuit (network).Definition 1.
LetλVλ,Eλ be an electric circuit, where Vλ and Eλ are the sets of nodes (vertices) and branches (edges), respectively. The order of the electric circuit is Vλ and the size of the circuit is Eλ).
Figure1 demonstrates the example of the electric circuit and its equivalent graph.
Slater and Harary described the concept of resolving sets (RSs) independently in graphs [1–3], respectively. Metric basis have been used in robot navigation [4], chemical structures [5], and computed networks [6]. An electric circuit will stop working if one node of the circuit becomes faulty. Hernando et al. [7] established the new invariant FTRS to resolve such complications. If the removal of one node from the RS results in another RS, then the RS is called the FTRS. In this situation, a FTRS solves the problem by efficiently flowing the current in the circuit when one of the nodes stops working. The minimum cardinality of FTRS is known as the FTMD. Due to the generalized invariant, the FTMD produces more efficient results than MD. Due to this fact, researchers started to give attention to computing the exact values of the FTMD for different families of graphs.
Hernando et al. [7] discussed the invariant FTMD for the tree graphs and computed the upper bound β′G≤βG1+2.5βG−1 for any graph G. Raza et al. [8], Zheng et al. [9], and Afzal et al. [10] applied the concept of the FTMD in some families of convex polytopes and computed their exact values. Basak et al. [11] calculated this parameter for the graph Cn1,2,3, and Saha et al. [12] generalized the results for the graph Cn1,2,3,4. Hayat et al. [13] and Prabhu et al. [14] applied this invariant to different computer networks and found their upper bounds. Somasundari et al. [15], Azeem et al. [16], Ahmad et al. [17], and Nadeem et al. [18] used the FTMD on different chemical structures and computed the exact values of this parameter. Laxman in [19] computed the lower bound of the FTMD for the cube of the path graph. Koam et al., in [20], calculated the MD and FTMD of the hollow coronoid chemical structure. Wang et al., in [21], considered the problem of finding the FTMD of three types of ladder graphs. Sharma and Bhat, in [22], calculated the FTMD of three families of the double antiprism graphs, which equals to 4. For more applications of the FTMD, see [23–25].
Voronov [26] and Raza et al. [27] determined some important upper bounds for the king’s and extended Petersen graphs, respectively. Guo et al. [28] computed the FTMD for the line graphs of the families of necklace and prism graphs. Faheem et al. [29] calculated this invariant for the subdivision graphs of the same families of graphs. Simic et al. [30] and Saha et al. [31] determined the precise value of the FTMD for the grid and square of grid graphs, respectively. Ahmad et al. [32] calculated this parameter for Pn,2⊙K1 graph, which equals to 4. Hussain et al. [33] applied the idea of the FTMD to some families of gear graphs. For more applications and results about the FTMD in engineering, we refer [34–36].
The following are some essential terminologies and definitions that assist in calculating our primary results.Figure 1
Electric circuit and its equivalent graph.Definition 2.
The degree″dλξ″ of ″ξ″ is the cardinality of branches that is incident to a node in ξ∈Vλ.Definition 3.
The minimum cardinality of the branches, betweenξ1−ξ2 path, is known as the distance dλξ1,ξ2 between ξ1,ξ2∈Vλ.Definition 4.
Letκ=ξ1,ξ2,…,ξt⊂Vλ; then, the absolute difference code have t -vector dλμ1,ξ1−dλμ2,ξ1,…,dλμ1,ξt−dλμ2,ξt for any μ1,μ2∈Vλ with respect to κ, denoted by ADμ1,μ2|κ.Definition 5.
Letκ=ξ1,ξ2,…,ξt⊂Vλ; then, the t-order distance code rμ|κ for a node μ∈Vλ is dλμ,ξ1,dλμ,ξ2,…,dλμ,ξt with respect to κ. If the distance codes for every nodes of the circuit are unique, then the set κ is said to be a RS of the circuit λ. Moreover, if the absolute difference codes for any two nodes of the circuit have at least one nonzero with respect to κ, then κ is called the RS. The minimum cardinality of κ is called the MD, denoted by βλ.Definition 6.
Any RSκ′ of the circuit λ is known as the FTRS of the circuit if κ′∖ξ is again a RS of the circuit, where ξ∈κ′. Moreover, if the absolute difference codes for any two nodes of the circuit have at least two nonzeros with respect to κ′, then κ′ is called the FTRS. The minimum cardinality of κ′ is called the FTMD, denoted by β′λ.Definition 7.
The line graph of the circuitλ is a new circuit Lλ, whose nodes are the branches of λ and two branches υ1 and υ2 have a common end node in λ if and only if they are connected in Lλ.
Following are some important bounds forβ′λ which are presented.Lemma 1 (see [37]).
Letλ be any graph; then, βλ<β′λ.Lemma 2 (see [37]).
Letλ≠Pn be any graph; then, β′λ≥3.Lemma 3.
If the FTMD of any graphλ is 3 and ξ1,ξ2,ξ3⊂Vλ is a FTRS in λ, then the degrees of the vertices ξ1,ξ2,ξ3 are no more than 3.


## 2. The Fault-Tolerant Resolvability of the Line Graph of Dragon Graph

LetCn be a cycle with edge set ECn=e1,e2,…,en; also, let Pm+1 be a path with edge set EPm+1=f1,f2,…,fm. Dragon graph Tn,m is shown in Figure 2.Figure 2
Dragon graphT9,5.Figure 3
Line graph of dragon graphT9,5.To compute our required results, we convert the graphTn,m into their line graph LTn,m. The line graph LTn,m of the dragon graph consists of a cycle of nodes e1,e2,…,en and the path of nodes f1,f2,…,fm, as shown in Figure 3.The result of the MD ofLTn,m is presented below.Theorem 1.
For any integersm≥1 and n≥4, we have βLTn,m=2.Proof.
For even integersn≥4, it can be easily verify that κ=e1,en+4/2⊂VLTn,m is the metric generator of LTn,m. For odd integers n≥5, it can also be verified that κ=e1,en+1/2⊂VLTn,m is the metric generator of LTn,m. So, βLTn,m=2.
Now, we will compute the FTMD forLTn,m.Theorem 2.
For any integersm≥1 and n≥4, we have β′LTn,m=3.Proof.
To calculate our required results, the following are the cases.Case 1.
Ifn is odd.
Takeκ′=e2,en+1/2,en+3/2⊂VLTn,m for odd integers n≥5. The distance codes of the nodes ek, where 1≤k≤n, are(1)rek|κ′=1,−1+n2,−1+n2,ifk=1,−2+k,n+2k−12,−2k+n+32,if2≤k≤3+n2,−k+n+2,−n+2k−12,−n+2k−32,if5+n2≤k≤n.
The distance codes for the nodesfk are  rfk|κ′=k+1,−1+n+2k/2,−3+n+2k/2, for 1≤k≤m.
From the above codes, we can conclude that the absolute difference codes for every pair of nodes have at least two nonzero in their 3-vector. So,β′LTn,m≤3. From Lemma 1 and Theorem 1, we have β′LTn,m≥3. Hence, β′LTn,m=3.Case 2.
Ifn is even.
Takeκ′=e1,en+4/2,f1⊂VLTn,m for every even integers n≥4. The distance codes of the nodes ek, where 1≤k≤n, are(2)rek|κ′=0,−2+n2,1,ifk=1,−1+k,|−n+2k−42|,k,if2≤k≤n2,−k+n+1,|−n+2k−42,−k+n+1,ifn+22≤k≤n.
The distance codes for the nodesfk with respect to W′ are  rfk|κ′=k,−4+n+2k/2,−1+k, for 1≤k≤m.
From the above codes, we can conclude that the absolute difference codes for every pair of nodes have at least two nonzero in their 3-vector. This shows thatβ′LTn,m≤3, and from Lemma 2, β′LTn,m≥3. Hence, β′LTn,m=3.


## 3. The Fault-Tolerant Resolvability of the Line Graph of Kayak Paddles Graph

Kayak paddles graphKPl,m,n is a graph made up of two cycles Cl and Cm having size l and m joined by a path of length n. We label the branches of cycle Cl by e1,e2,…,el, the branches of cycle Cm by f1,f2,…,fm, and the branches of path joining these cycles by h1,h2,…,hn, as shown in Figure 4.Figure 4
Kayak paddle graphKP9,7,6.To compute our required results, we need to convert the graphKPl,m,n into the graph LKPl,m,n. The line graph of kayak paddles graph LKPl,m,n consists of cycle Cl with nodes e1,e2,…,el, the cycle Cm with nodes f1,f2,…,fm, and the nodes of path joining these cycles h1,h2,…,hn, as shown in Figure 5.Figure 5
Line graphLKP9,7,6.The known result aboutβLKPl,m,n is presented below.Theorem 3 (see [38]).
For any integersn≥2 and l,m≥3, we have βLKPl,m,n=2.Now, we will computeβ′LKPl,m,n.Theorem 4.
For any integersn≥2 and l,m≥3, we have β′LKPl,m,n=4.Proof.
To calculate our required results, the following are the cases.Case 3.
Ifl and m both are even.
Takeκ′=e1,e2,f1,f2⊂VLKPl,m,n for both even integers l,m≥4. The distance codes of the nodes ek, where 1≤k≤l, are(3)rek|κ′=−1+k,|−k+2|,k+n,1+n+k,if1≤k≤l2,l2,−2+l2,l+2n2,2+l+2n2,ifk=2+l2,−k+l+1,−k+l+2,−k+l+n+1,−k+2+l+n,if4+l2≤k≤l.
The distance codes for the nodesfk, where 1≤k≤m, are(4)rfk|κ′=k+n,1+n+k,−1+k,|−2+k|,if1≤k≤m2,m+2n2,2+m+2n2,m2,−2+m2,ifk=2+m2,−k+1+m+n,−k+2+m+n,−k+m+1,−k+2+m,ifm+42≤k≤m.
The distance codes for the nodeshk are     rhk|κ′=k,1+k,−k+1+n,−k+2+n, for 1≤k≤n.
From the above codes, we can conclude that the absolute difference codes for every pair of nodes have at least two nonzeros in their 4-vector. This shows thatβ′LKPl,m,n≤4, but, in Lemma 2, β′LKPl,m,n≥3.
Now, to prove thatβ′LKPl,m,n≥4, suppose contrary that β′LKPl,m,n=3, and according to Lemma 3, we have the following conditions:(i)
Letκ′=ei,ej,ek⊂VLKPl,m,n, for 1≤i<j<k≤l; then, ADf1,fm|κ′=0,0,0. So, κ′ is not FTRS.(ii)
Letκ′=ei,fj,fk⊂VLKPl,m,n, for 1≤i≤l and 1≤j<k≤m; then, ADe1,el|κ′=1,0,0. So, κ′ is not FTRS.(iii)
Letκ′=ei,ej,hk⊂VLKPl,m,n, for 1≤i<j≤l and 1≤k≤n; then, ADf1,fm|κ′=0,0,0. So, κ′ is not FTRS.(iv)
Letκ′=ei,hj,hk⊂VLKPl,m,n, for 1≤i≤l and 1≤j<k≤n; then, ADf1,fm|κ′=0,0,0. So, κ′ is not FTRS.(v)
Letκ′hi,hj,hk⊂VLKPl,m,n, for 1≤i<j<k≤n; then, ADe1,el|κ′=0,0,0. So, κ′ is not FTRS.
From the above discussion, we conclude that there is no FTRS with cardinality 3. This shows thatβ′LKPl,m,n≥4. Hence, β′LKPl,m,n=4.Case 4.
Ifl and m both are odd.(1)
Letl=3, and for any odd integers m≥3, take κ′=e1,e3,f1,fm+3/2⊂VLKP3,m,n. The distance codes for the nodes ek, where 1≤k≤3, are(5)rek|κ′=−1+k,1,k+n,−3+m+2k+2n2,if1≤k≤2,1,0,1+n,−1+m+2n2,ifk=3.The distance codes for the nodesfk, where 1≤k≤m, are(6)rfk|κ′=1+n,1+n,0,−1+m2,ifk=1,k+n,n+k,−1+k,−2k+m+32,if2≤k≤1+m2,−k+1+m+n,−k+1+m+n,−k+m+1,−3−m+2k2,if3+m2≤k≤m.The distance codes for the nodeshk are rhk|κ′=k,k,−k+n+1,−2k−1m+2n/2, for 1≤k≤n.(2)
Takeκ′=e1,e2,f1,f2⊂VLKPl,m,n, for both odd integers l,m≥5. The distance codes for the nodes ek, where 1≤k≤l, are(7)rek|κ′=−1+k,|−2+k|,n+k,1+n+k,if1≤k≤l+12,−1+l2,−1+l2,−1+l+2n2,1+l+2n2,ifk=3+l2,−k+1+l,−k+l+2,−k+l+n+1,−k+2+l+n,if5+l2≤k≤l.
The distance codes for the nodesfk, where 1≤k≤m, are(8)rfk|κ′=k+n,1+n+k,−1+k,|−k+2|,if1≤k≤1+m2,−1+m+2n2,1+m+2n2,−1+m2,−1+m2,ifk=3+m2,−k+1+m+n,−k+2+m+n,−k+1+m,−k+2+m,if5+m2≤k≤m.
The distance codes for the nodeshk are      rhk|κ′=k,1+k,−k+1+n,−k+2+n, for 1≤k≤n.
From the above codes, we can conclude that the absolute difference codes for every pair of nodes have at least two nonzeros in their 4-vector. This shows thatβ′LKPl,m,n≤4, but in Lemma 2, β′LKPl,m,n≥3.
Now, to prove thatβ′LKPl,m,n≥4, suppose contrary that β′LKPl,m,n=3, and according to Lemma 3, we have the following conditions:(i)
Letκ′=ei,ej,ek⊂VLKPl,m,n, for 1≤i<j<k≤l; then, ADf1,fm|κ′=0,0,0. So, κ′ is not FTRS.(ii)
Letκ′=ei,fj,fk⊂VLKPl,m,n; for 1≤i≤l and 1≤j<k≤m, then(9)ADe1,el|κ′=0,0,0,ifi=l+12,1,0,0,else.So,κ′ is not FTRS.(iii)
Letκ′=ei,ej,hk⊂VLKPl,m,n; for 1≤i<j≤l and 1≤k≤n, then ADf1,fm|κ′=0,0,0. So, κ′ is not FTRS.(iv)
Letκ′=ei,hj,hk⊂VLKPl,m,n; for 1≤i≤l and 1≤j<k≤n, then ADf1,fm|κ′=0,0,0. So, κ′ is not FTRS.(v)
Letκ′=hi,hj,hk⊂VLKPl,m,n; for 1≤i<j<k≤n, then ADe1,el|κ′=0,0,0. So, κ′ is not FTRS.
From the above discussion, we conclude that there is no FTRS with cardinality 3. This shows thatβ′LKPl,m,n≥4. Hence, β′LKPl,m,n=4.Case 5.
Ifm is even and l is odd.(i)
Letl=3, and for any even integers m≥4, take κ′=e1,e3,f1,f2⊂VLKP3,m,n. The distance codes for the nodes ek, where 1≤k≤3, are(10)rek|κ′=−1+k,1,k+n,1+n+k,if1≤k≤2,1,0,1+n,2+n,ifk=3.The distance codes for the nodesfk, where 1≤k≤m, are(11)rfk|κ′=n+k,k+n,−1+k,|−k+2|,if1≤k≤m2,m+2n2,m+2n2,m2,−2+m2,ifk=2+m2,−k+1+m+n,−k+1+m+n,−k+m+1,−k+m+2,if4+m2≤k≤m.The distance codes for the nodeshk arerhk|κ′=k,k,−k+n+1,−k+n+2, for 1≤k≤n.(2)
Takeκ′=e1,e2,f1,f2⊂VLKPl,m,n for any odd l≥5 and even m≥4 integers. The distance codes for the nodes ek, where 1≤k≤l, are(12)rek|κ′=−1+k,|−k+2|,k+n,1+n+k,if1≤k≤1+l2,−1+l2,−1+l2,−1+l+2n2,1+l+2n2,ifk=l+32,−k+l+1,−k+l+2,−k+1+l+n,−k+2+l+n,ifl+52≤k≤l.
The distance codes for the nodesfk, where 1≤k≤m, are(13)rfk|κ′=k+n,1+n+k,−1+k,|−k+2|,if1≤k≤m2,m+2n2,2+m+2n2,m2,−2+m2,ifk=2+m2,−k+1+m+n,−k+2+m+n,−k+1+m,−k+2+m,if4+m2≤k≤m.
The distance codes for the nodeshW are
rhk|W′=k,1+k,−k+1+n,−k+2+n, for 1≤k≤n.
From the above codes, we can conclude that the absolute difference codes for every pair of nodes have at least two nonzeros in their 4-vector. This shows thatβ′LKPl,m,n≤4, but, in Lemma 2, β′LKPl,m,n≥3.
Now, to proveβ′LKPl,m,n≥4, suppose contrary that β′LKPl,m,n=3, and according to Lemma 3, we have the following conditions:(i)
Letκ′=ei,ej,ek⊂VLKPl,m,n, for 1≤i<j<k≤l; then, ADf1,fm|κ′=0,0,0. So, κ′ is not FTRS.(ii)
Letκ′=ei,fj,fk⊂VLKPl,m,n, for 1≤i≤l and 1≤j<k≤m; then,(14)ADe1,el|κ′=0,0,0,ifi=l+12,1,0,0,else.So,κ′ is not FTRS.(iii)
Letκ′=ei,ej,hk⊂VLKPl,m,n, for 1≤i<j≤l and 1≤k≤n; then, ADf1,fm|κ′=0,0,0. So, κ′ is not FTRS.(iv)
Letκ′=ei,hj,hk⊂VLKPl,m,n, for 1≤i≤l and 1≤j<k≤n; then, ADf1,fm|κ′=0,0,0. So, κ′ is not FTRS.(v)
Letκ′=hi,hj,hk⊂VLKPl,m,n, for 1≤i<j<k≤n; then, ADe1,el|κ′=0,0,0. So, κ′ is not FTRS.
From the above discussion, we conclude that there is no FTRS with cardinality 3. This shows thatβ′LKPl,m,n≥4. Hence, β′LKPl,m,n=4.


## 4. Conclusion

We conclude that, in the case of the line graph for the dragon graph, the FTMD is exactly one more than its MD, and it exactly doubles the MD in the case of the line graph of kayak paddles graph [39–44].



---

*Source: 7688702-2022-04-13.xml*