# Fault-Tolerant Partition Resolvability of Cyclic Networks

Authors: Kamran Azhar; Sohail Zafar; Agha Kashif; Michael Onyango Ojiema
Journal: Journal of Mathematics
 (2021)

---

## Abstract

Graph invariants provide an amazing tool to analyze the abstract structures of networks. The interaction and interconnection between devices, sensors, and service providers have opened the door for an eruption of mobile over the web applications. Structure of web sites containing number of pages can be represented using graph, where web pages are considered to be the vertices, and an edge is a link between two pages. Figuring resolving partition of the graph is an intriguing inquest in graph theory as it has many applications such as sensor design, compound classification in chemistry, robotic navigation, and Internet network. The partition dimension is a graph parameter akin to the concept of metric dimension, and fault-tolerant partition dimension is an advancement in the line of research of partition dimension of the graph. In this paper, we compute fault-tolerant partition dimension of alternate triangular cycle, mirror graph, and tortoise graphs.


---

## Body

## 1. Introduction and Basic Terminologies

Graph theory is an intense region of arithmetic that has capacious variety of implementations in numerous regions of science, such as chemistry, biology, software engineering, and electrical and hardware engineering. Graphing is a powerful tool for representing and understanding objects and their relationships. Currently, online social networks are considered as an essential element for interpersonal relationships where people and smart objects are connected together in smart environments. Theoretical principles of graph theory are applied to practical fields, by determining graph invariants such as vertices, edges, diameter, and degree and mapping them to real-time problems. These invariants are the supporting tools between science and engineering or computational techniques in the fields of chemical, electrical, computer, and telecommunication engineering. One concept that pervades all the graph theory is that of distance and is used in isomorphism testing, graph operations, maximal and minimal problems on connectivity, and diameter. Metric dimension is one of the distance related parameter in graphs that has attracted the attention of several researchers. The generalized version of metric dimension of the graph is unique and an important parameter of graph theory called partition dimension of the graph. It is considered as an applied topic of graph theory and has applications in structure-activity issues in drug design, network discovery and verification [5], pattern recognition and image processing [16], and modelling of chemical substances [14].In 2000, the concept of partition dimension of graph was initiated by Chartrand et al. as an extension of metric dimension of the graph [6]. Let Ω be a connected graph of order n with vertex set VΩ and edge set EΩ. If two vertices w,z∈VΩ, then the length of shortest path between w and z in Ω is distance between these vertices and is denoted by dw,z. The distance between a vertex z and J⊆VΩ is defined as mindz,y|y∈J and is denoted by dz,J. For a vertex z∈VΩ, Nz will denote the open neighbourhood of z in Ω, i.e.,Nz=q∈VΩ:qis adjacent toz, and closed neighbourhood of z will be denoted by Nz=Nz∪z [18]. Let μ=z1,z2,…,zp be an ordered subset of vertex set of Ω. The representation of z with respect to μ is p tuple dz,z1,dz,z2,…,dz,zp and is denoted by rz|μ. The subset μ is called a resolving set of Ω if distinct vertices of Ω have distinct representations with respect to μ. The metric dimension of Ω is defined as minμ:μis resolving set ofΩ and is denoted by βΩ. Ali et al. discussed that path-related graphs have constant metric dimension [1]. Zuo et al. computed constant metric dimension of some generalized convex polytopes [27]. Rehman et al. computed the metric dimension of arithmetic graph of a composite number [20]. In 2021, metric dimension of windmill graph was computed by Singh et al. [24].In 2008, Hernando et al. initiated the concept of fault-tolerant metric dimension of graphs [10]. If, for every pair of distinct vertices q,z∈VΩ, there exists at least two vertices α1,α2∈μ such that dq,δi≠dz,δi for i∈1,2, then the resolving set μ of VΩ is called fault tolerant. The fault-tolerant metric dimension of Ω is the minimum cardinality of fault-tolerant resolving set μ and is denoted by β′Ω. Ahmad et al. computed fault-tolerant metric dimension of Pn,2⊙K1 graph [3]. Hayat et al. discussed fault-tolerant metric dimension of interconnection networks [9].Letξ=ξ1,ξ2,…,ξp be a partition with p partition classes of vertex set of connected graph Ω. The representation of vertex z with respect to partition set ξ is p vector dz,ξ1,dz,ξ2,…,dz,ξp denoted by rz|ξ. The partition ξ is called resolving partition of Ω if representation of all the vertices in Ω is different. We define the partition dimension of graph Ω as minξ:ξis resolving partition ofΩ and is denoted by pdΩ. Chartrand et al. [6] characterised the graphs having pdΩ to be 2 or n. For various classes of connected graphs, the partition dimension has been obtained. For instance, Ayesha et al. computed the partition dimension of trihexagonal α boron nanotube [23]. Mehreen et al. computed the partition dimension of the fullerene graph [15]. Hussain et al. provided the bounds on partition dimension of generalized Mobius ladder [11]. Monica et al. studied the partition dimension problem for certain classes of the series-parallel graph [17]. Chu et al. calculated the sharp bounds for partition dimension of convex polytopes [7]. Wei et al. studied the partition dimension problem for cycle-related graphs [25]. Yero et al. studied the partition dimension of strong product graphs and Cartesian product graphs [26].Gary et al. and Khuller et al. mentioned the computational complexity of metric dimension of general graphs [8, 13]. Computation of pdΩ is more complex as it is more harder than computing metric dimension of a graph.The concept of fault-tolerant partition dimension of the graph was initiated by Salman et al. [22]. Let ξ=ξ1,ξ2,…,ξp be a partition with p partition classes of the vertex set of connected graph Ω. The partition ξ is called fault-tolerant resolving partition of Ω if for every pair of distinct vertices y,z∈VΩ, and ry|ξ and rz|ξ differ by at least two places. The fault-tolerant partition dimension of Ω is defined as minξ:ξis fault−tolerant resolving partition ofΩ and is denoted by ℱΩ. Imran et al. characterised that ℱΩ of all the graphs of order n is n−1 [12]. Kamran et al. computed the ℱΩ of homogeneous caterpillar, tadpole, and necklace graphs [2, 4]. Asim et al. computed ℱΩ of circulant graphs with connection set 1,2 in [19]. In this paper, we extend this study by considering alternate triangular cycle, mirror graph, and tortoise graphs and show that they have constant fault-tolerant partition dimension.Chartrand et al. revealed the following basic results onpdΩ.Proposition 1 (see [6]).
LetΩ be a graph; then,(1)
pdΩ≤βΩ+1(2)
pdΩ=2 if Ω=Pn, where Pn is a path(3)
pdΩ=n if Ω=Kn, where Kn is the complete graphSalman et al. revealed the following basic results onℱΩ.Proposition 2 (see [21]).
Forn≥2,(1)
pdΩ≤ℱΩ(2)
ℱΩ=n if Ω≅Kn or Ω≅Kn−eProposition 3 (see [22]).
(1)
Forn≥2, ℱΩ≤β′Ω+1(2)
Forn≥3, 3≤ℱΩ≤nThe remaining part of the paper is structured in the following manner. In Section2, we are concerned with the computation of ℱAC2n, ℱMrPn, and ℱTn, where AC2n, MrPn, and Tn are alternate triangular cycle, mirror graph, and tortoise graphs, respectively. Finally, we conclude the paper in Section 3, by giving future research direction.


## 2. Fault-Tolerant Partition Dimension of Alternate Triangular Cycle

In this section, we computeℱAC2n, where AC2n is alternate triangular cycle. Vertices of AC2n, for n≥3, are divided into three sets, D=dϱ:1≤ϱ≤n, E=eϱ:1≤ϱ≤n, and F=fϱ:1≤ϱ≤n. An alternate triangular cycle AC2n is obtained by replacing alternate edge of an even cycle C2n by C3. The set VAC2n=D∪E∪F and EAC2n=dϱeϱ:1≤ϱ≤n∪eϱdϱ+1:1≤ϱ≤n−1∪d1en∪dϱfϱ:1≤ϱ≤n∪eϱfϱ:1≤ϱ≤n are vertex set and edge set of alternate triangular cycle, respectively. Order of AC2n is 3n. The alternate triangular cycle AC12 is shown in Figure 1.Figure 1
Alternate triangular cycleAC12.We computepdAC2n and HTML translation failed in the following theorems.Theorem 1.
The partition dimension of alternate triangular cycleAC2n, for n≥2, is 3.Proof.
Letξ=ξ1,ξ2,ξ3 be a partition with 3 partition classes of vertex set of AC2n for n≥2. For n=2, we consider ξ1=d1, ξ2=e1, and ξ3=d2,e2,f1,f2. It can easily be observed that ξ is resolving partition.Case 1: forn=3δ, δ≥1, rw|ξ, where ξ1=dϱ:1≤ϱ≤n∪eϱ:1≤ϱ≤n∪fϱ:1≤ϱ≤δ, ξ2=fϱ:δ+1≤ϱ≤2δ, and ξ3=fϱ:2δ+1≤ϱ≤n are shown as follows:(1)rdϱ|ξ=0,2δ−2ϱ+3,2ϱ,1≤ϱ≤δ,0,1,n+δ−2ϱ+3,δ+1≤ϱ≤2δ,0,2ϱ−n−δ,1,2δ+1≤ϱ≤n,reϱ|ξ=0,2δ−2ϱ+2,2ϱ+1,1≤ϱ≤δ,0,1,n+δ−2ϱ+2,δ+1≤ϱ≤2δ,0,2ϱ−n−δ+1,1,2δ+1≤ϱ≤n,rfϱ|ξ=0,2δ−2ϱ+3,2ϱ+1,1≤ϱ≤δ,1,0,n+δ−2ϱ+3,δ+1≤ϱ≤2δ,1,2ϱ−n−δ+1,0,2δ+1≤ϱ≤n.Case 2: forn=3δ+1, δ≥1, rw|ξ, where ξ1=dϱ:1≤ϱ≤n∪eϱ:1≤ϱ≤n∪fϱ:1≤ϱ≤δ+1, ξ2=fϱ:δ+2≤ϱ≤2δ+1, and ξ3=fϱ:2δ+2≤ϱ≤n are shown as follows:(2)rdϱ|ξ=0,2δ+2,2,ϱ=1,0,2δ−2ϱ+5,2ϱ,2≤ϱ≤δ+1,0,1,n+δ−2ϱ+4,δ+2≤ϱ≤2δ+1,0,2ϱ−n−δ−1,1,2δ+2≤ϱ≤n,reϱ|ξ=0,2δ−2ϱ+4,2ϱ+1,1≤ϱ≤δ,0,2,2δ+2,ϱ=δ+1,0,1,n+δ−2ϱ+3,δ+2≤ϱ≤2δ+1,0,2ϱ−n−δ,1,2δ+2≤ϱ≤n,rfϱ|ξ=0,2δ−2ϱ+5,2ϱ+1,1≤ϱ≤δ+1,1,0,n+δ−2ϱ+4,δ+2≤ϱ≤2δ+1,1,2ϱ−n−δ,0,2δ+2≤ϱ≤n.Case 3: forn=3δ+2, δ≥1, rw|ξ, where ξ1=dϱ:1≤ϱ≤n∪eϱ:1≤ϱ≤n∪fϱ:1≤ϱ≤δ+1, ξ2=fϱ:δ+2≤ϱ≤2δ+2, and ξ3=fϱ:2δ+3≤ϱ≤n are shown as follows:(3)rdϱ|ξ=0,2δ+2,2ϱ=1,0,2δ−2ϱ+5,2ϱ2≤ϱ≤δ+1,0,1,n+δ−2ϱ+5δ+2≤ϱ≤2δ+2,0,2ϱ−n−δ−2,12δ+3≤ϱ≤n,reϱ|ξ=0,2δ−2ϱ+4,2ϱ+11≤ϱ≤δ+1,0,1,n+δ−2ϱ+4δ+2≤ϱ≤2δ+2,0,2ϱ−n−δ−1,12δ+3≤ϱ≤n,rfϱ|ξ=0,2δ−2ϱ+5,2ϱ+1,1≤ϱ≤δ+1,1,0,n+δ−2ϱ+5,δ+2≤ϱ≤2δ+2,1,2ϱ−n−δ−1,0,2δ+3≤ϱ≤n.
It is obvious from the above distinct representations thatξ is resolving partition of AC2n; therefore, pdAC2n≤3. It follows from Proposition 1(b) that pdAC2n≥3. This completes the proof.Theorem 2.
The fault-tolerant partition dimension of alternate triangular cycleAC2n, for n≥2, is 4.Proof.
In order to prove thatℱAC2n=4, first, we show that ℱAC2n≤4. In this regard, consider ξ=ξ1,ξ2,ξ3,ξ4 be a partition with 4 partition classes of vertex set of AC2n, for n≥2. For n=2, consider ξ1=d1, ξ2=e1,d2, ξ3=e2, and ξ4=f1,f2. It is easy to observe that ξ is fault-tolerant resolving partition. (1)
Case 1: forn=3δ, δ≥1, rw|ξ, where ξ1=dϱ:1≤ϱ≤n∪eϱ:1≤ϱ≤n, ξ2=fϱ:1≤ϱ≤δ, ξ3=fϱ:δ+1≤ϱ≤2δ, and ξ4=fϱ:2δ+1≤ϱ≤n are shown as follows:(4)rdϱ|ξ=0,1,2δ−2ϱ+3,2ϱ,1≤ϱ≤δ,0,2ϱ−n+δ,1,n+δ−2ϱ+3,δ+1≤ϱ≤2δ,0,2n−2ϱ+3,2ϱ−n−δ,1,2δ+1≤ϱ≤n,reϱ|ξ=0,1,2δ−2ϱ+2,2ϱ+1,1≤ϱ≤δ,0,2ϱ−n+δ+1,1,n+δ−2ϱ+2,δ+1≤ϱ≤2δ,0,2n−2ϱ+2,2ϱ−n−δ+1,1,2δ+1≤ϱ≤n,rfϱ|ξ=1,0,2δ−2ϱ+3,2ϱ+1,1≤ϱ≤δ,1,2ϱ−n+δ+1,0,n+δ−2ϱ+3,δ+1≤ϱ≤2δ,1,2n−2ϱ+3,2ϱ−n−δ+1,0,2δ+1≤ϱ≤n.(2)
Case 2: forn=3δ+1, δ≥1, rw|ξ, where ξ1=dϱ:1≤ϱ≤n∪eϱ:1≤ϱ≤n−1, ξ2=en∪fϱ:1≤ϱ≤δ, ξ3=fϱ:δ+1≤ϱ≤2δ, and ξ4=fϱ:2δ+1≤ϱ≤n are shown as follows:(5)rdϱ|ξ=0,1,2δ−2ϱ+3,2ϱ,1≤ϱ≤δ,0,2ϱ−n+δ+1,1,n+δ−2ϱ+2,δ+1≤ϱ≤2δ,0,2n−2ϱ+1,2ϱ−n−δ+1,1,2δ+1≤ϱ≤n,reϱ|ξ=0,1,2δ−2ϱ+2,2ϱ+1,1≤ϱ≤δ,0,2ϱ−n+δ+2,1,n+δ−2ϱ+1,δ+1≤ϱ≤2δ,0,2n−2ϱ,2ϱ−n−δ+1,1,2δ+1≤ϱ≤n−1,1,0,2ϱ+2,1,ϱ=n,rfϱ|ξ=1,0,2δ−2ϱ+3,2ϱ+1,1≤ϱ≤δ,1,2ϱ−n+δ+2,0,n+δ−2ϱ+2,δ+1≤ϱ≤2δ,1,2n−2ϱ+1,2ϱ−n−δ+2,0,2δ+1≤ϱ≤n.(3)
Case 3: forn=3δ+2, δ≥1, rw|ξ, where ξ1=dϱ:1≤ϱ≤n∪eϱ:1≤ϱ≤n∪f1, ξ2=fϱ:2≤ϱ≤δ+1, ξ3=fϱ:δ+2≤ϱ≤2δ+2, and ξ4=fϱ:2δ+3≤ϱ≤n are shown as follows:(6)rdϱ|ξ=0,3,2δ+2,2,ϱ=1,0,1,2δ−2ϱ+5,2ϱ,2≤ϱ≤δ+1,0,2ϱ−n+δ,1,n+δ−2ϱ+5,δ+2≤ϱ≤2δ+2,0,2n−2ϱ+5,2ϱ−n−δ−2,1,2δ+3≤ϱ≤n,reϱ|ξ=0,2,2δ+2,3,ϱ=1,0,1,2δ−2ϱ+4,2ϱ+1,2≤ϱ≤δ+1,0,2ϱ−n+δ+1,1,n+δ−2ϱ+4,δ+2≤ϱ≤2δ+2,0,2n−2ϱ+4,2ϱ−n−δ−1,1,2δ+3≤ϱ≤n,rfϱ|ξ=0,3,2δ+3,3,ϱ=1,1,0,2δ−2ϱ+5,2ϱ+1,2≤ϱ≤δ+1,1,2ϱ−n+δ+1,0,n+δ−2ϱ+5,δ+2≤ϱ≤2δ+2,1,2n−2ϱ+5,2ϱ−n−δ−1,0,2δ+3≤ϱ≤n.
It is obvious from the above distinct representations thatξ is fault-tolerant resolving partition of AC2n, so ℱAC2n≤4.
Now, we prove thatℱAC2n≥4. For this, we show that ℱAC2n≠3. For a contradiction, suppose ξ=ξ1,ξ2,ξ3 be a fault-tolerant partition basis of AC2n. There will be at least one vertex of degree 3 in one of the partition set ξ1,ξ2, or ξ3. Without loss of generality, we assume that dϱ is a vertex of degree 3 that belongs to ξ1, and Ndϱ=eϱ,eϱ+j,fϱ. Suppose that ξ1=1, and Ndϱ⊆ξ2∪ξ3, Ndϱ∩ξ2≥2, or Ndϱ∩ξ3≥2. Without loss of generality, we assume that, at least two vertices, s,t∈Ndϱ∩ξ2. As rs|ξ=1,0,k1 and rt|ξ=1,0,k2 are identical at two places, hence, it is a contradiction.
We consider the following cases whenξ1≥2 and dϱ∈ξ1.(1)
Case 1: ifNdϱ∩ξ1=eϱ,eϱ+j,fϱ, then rdϱ|ξ=0,b0,c0, reϱ|ξ=0,b1,c1, reϱ+j|ξ=0,b2,c2, and rfϱ|ξ=0,b3,c3. As b0−1≤b1,b2,b3≤b0+1, so using Pigeonhole principle, there will be similarity in the representation of two vertices at two places; hence, it is a contradiction.(2)
Case 2: if two neighbours ofdϱ∈ξ1 and one neighbour of dϱ belongs to ξ2, then following cases will arise:(1)
Case 2(a): ifNdϱ∩ξ1=eϱ,eϱ+j and one vertex fϱ∈ξ2, then rdϱ|ξ=0,1,c0 and reϱ|ξ=0,1,c1. As representation of two vertices has two identical coordinates, hence, it is a contradiction.(2)
Case 2(b): ifNdϱ∩ξ1=eϱ,fϱ and one vertex eϱ+j∈ξ2, then, rdϱ|ξ=0,1,c0, reϱ|ξ=0,b1,c1, and rfϱ|ξ=0,2,c2. Since 1≤b1≤2, so representation of two vertices will have two identical coordinates, hence, it is a contradiction.(3)
Case 2(c): ifNdϱ∩ξ1=eϱ+j,fϱ and one vertex eϱ∈ξ2, then rdϱ|ξ=0,1,c3, reϱ+j|ξ=0,b2,c4, and rfϱ|ξ=0,2,c5. Since 1≤b2≤2, so representation of two vertices have two identical coordinates; hence, it is a contradiction.(3)
Case 3: ifNdϱ∩ξ1=eϱ and two vertices eϱ+j,fϱ∈ξ2, then, rdϱ|ξ=0,1,c0, reϱ|ξ=0,1,c1, reϱ+j|ξ=1,0,c2, and rfϱ|ξ=1,0,c3. Since representation of two vertices has two identical coordinates, thus, it is a contradiction.(4)
Case 4: when each ofξ1,ξ2, and ξ3 contains one neighbour of dϱ, then we have following cases:(1)
Case 4(a): ifNdϱ∩ξ1=eϱ, eϱ+j∈ξ2, and fϱ∈ξ3, then rdϱ|ξ=0,1,1 and reϱ|ξ=0,c1,1, which leads to a contradiction.(2)
Case 4(b): ifNdϱ∩ξ1=eϱ+j, eϱ∈ξ2 and fϱ∈ξ3, then rdϱ|ξ=0,1,1 and reϱ+j|ξ=0,2,2. Since Neϱ+j=dϱ,dϱ+j,fϱ+j, so let dϱ+j,fϱ+j∈ξ1. Now, rfϱ+j|ξ=0,a1,b1, where 2≤a1,b1≤3, and rdϱ+j|ξ=0,a2,b2, where 1≤a2andb2≤3. It is obvious that representation of two vertices is identical at two places, so a contradiction.(5)
Case 5: ifNdϱ∩ξ1=∅, at least two vertices from Ndϱ belong to ξ2. Without loss of generality, we suppose that eϱ,eϱ+j∈ξ2; then, rdϱ|ξ=0,1,c0, reϱ|ξ=1,0,c1, and reϱ+j|ξ=1,0,c2. It is again a contradiction.
This discussion concludes the proof; hence,ℱAC2n≥4.Example 1.
Consider the alternate triangular cycleAC12, as shown in Figure 1. If ξ=ξ1,ξ2,ξ3,ξ4, where ξ1=dϱ:1≤ϱ≤6∪eϱ:1≤ϱ≤6, ξ2=f1,f2, ξ3=f3,f4, and ξ4=f5,f6 is a partition of VAC12, then the representations of vertices of AC12 are as follows: rd1|ξ=0,1,5,2, rd2|ξ=0,1,3,4, rd3|ξ=0,2,1,5, rd4|ξ=0,4,1,3, rd5|ξ=0,5,2,1, rd6|ξ=0,3,4,1, re1|ξ=0,1,4,3, re2|ξ=0,1,2,5, re3|ξ=0,3,1,4, re4|ξ=0,5,1,2, re5|ξ=0,4,3,1, re6|ξ=0,2,5,1, rf1|ξ=1,0,5,3, rf2|ξ=1,0,3,5, rf3|ξ=1,3,0,5, rf4|ξ=1,5,0,3, rf5|ξ=1,5,3,0, and rf6|ξ=1,3,5,0.
It can be seen from the above representations thatξ is a fault-tolerant resolving partition of AC12.


### 2.1. Fault-Tolerant Partition Dimension of Mirror Graph

Mirror graphMrPn is defined as the disjoint union of graph Ω and its copy Ω´ with additional edges joining each vertex of Ω to its corresponding vertex in Ω´. The set VMrPn=w1,w2,…,w2n and EMrPn=wlwl+1:1≤l≤n−1∪wn+lwn+l+1:1≤l≤n−1∪wlwn+l:1≤l≤n are vertex set and edge set of mirror graph, respectively. Mirror graph MrP4 is shown in Figure 2.Figure 2
Mirror graphMrP4.Yero et al. computed the partition dimension of the mirror graph in the following lemma.Lemma 1 (see [26]).
LetG be the mirror graph MrPn; then, pdMrPn=3.The following theorem allows us to computeℱMrPn.Theorem 3.
For everyn≥2,(7)ℱMrPn=3,ifnis2,4,otherwise.Proof.
Letξ=ξ1,ξ2,ξ3 be a partition set of vertices of MrPn for n=2. Considering ξ1=w1,w2, ξ2=w3, and ξ3=w4, it is easy to observe that ξ is fault-tolerant resolving partition of MrPn.
Now, forn≥3, consider ξ=ξ1,ξ2,ξ3,ξ4 be a partition with 4 partition classes of vertices of MrPn. rw|ξ, considering ξ1=wj:1≤j≤n−1, ξ2=wn, ξ3=wj:n+1≤j≤2n−1, and ξ4=w2n, are as follows:(8)rwϱ|ξ=0,n−ϱ,1,n−ϱ+1for1≤ϱ≤n−1,1,0,2,1forϱ=n,1,0,2n−ϱ+1,2n−ϱforn+1≤ϱ≤2n−1,2,1,1,0forϱ=2n.
As all the above representations are different, soξ is fault-tolerant resolving partition of MrPn; therefore, ℱMrPn≤4.
Now, we prove thatℱMrPn≥4; for this, we show that ℱMrPn≠3. For contradiction, let ξ=ξ1,ξ2,ξ3 be a fault-tolerant partition basis of MrPn. One of the partition sets contains at least one vertex of degree 3. Without loss of generality, we assume that wτ is a vertex of degree 3 that belongs to ξ1, and Nwτ=wp,wq,wr. Suppose that ξ1=1 and Nwτ⊆ξ2∪ξ3, Nwτ∩ξ2≥2, or Nwτ∩ξ3≥2. Without loss of generality, we assume that at least two vertices e1,e2∈Nwτ∩ξ2. As re1|ξ=1,0,k1 and re2|ξ=1,0,k2 have two identical coordinates, so it is a contradiction. Now, we discuss the following cases when ξ1≥2 and wτ∈ξ1.(1)
Case 1: ifNwτ∩ξ1=wp,wq,wr, then rwτ|ξ=0,b0,c0, rwp|ξ=0,b1,c1, rwq|ξ=0,b2,c2, and rwr|ξ=0,b3,c3. As b0−1≤b1,b2,b3≤b0+1, so using Pigeonhole principle, representation of two vertices have two identical coordinates; therefore, it is a contradiction.(2)
Case 2: ifNwτ∩ξ1=wp,wq and one vertex wr∈ξ2, then rwτ|ξ=0,1,c0, rwp|ξ=0,b1,c1, rwq|ξ=0,b2,c2, and rwr|ξ=1,0,c3. Since 1≤b1,b2≤2, so there will be similarity in the representation of two vertices at two places from ξ1 and ξ2; hence, it is a contradiction.(3)
Case 3: ifNwτ∩ξ1=wp and two vertices wq,wr∈ξ2, then rwτ|ξ=0,1,c0, rwp|ξ=0,b1,c1, rwq|ξ=1,0,c2, and rwr|ξ=1,0,c3. Since rwq|ξ and rwr|ξ have two identical coordinates, therefore, it is a contradiction.(4)
Case 4: ifNwτ∩ξ1=wp, wq∈ξ2, and wr∈ξ3, then Nwp=wτ,s1, Nwq=wτ,s1,s2, and Nwr=wτ,s2,s3. Let s1∈ξ1, s2∈ξ2 and s3∈ξ3, then rwτ|ξ=0,1,1 and rs1|ξ=0,1,c1, which leads to a contradiction. Now, let s1∈ξ1, s3∈ξ2, and s2∈ξ3; then, rwτ|ξ=0,1,1 and rs1|ξ=0,1,c1, which leads to a contradiction.(5)
Case 5: ifNwτ∩ξ1=∅ and at least two vertices from Nwτ belong to ξ2, without loss of generality, we suppose that wp,wq∈ξ2; then, rwτ|ξ=0,1,c0, rwp|ξ=1,0,c1, and rwq|ξ=1,0,c2. Again rwp|ξ and rwq|ξ have two identical coordinates, a contradiction.
The above discussions show thatℱMrPn≥4, which completes the proof.Example 2.
Consider the mirror graphMrP4, as shown in Figure 2. If ξ=ξ1,ξ2,ξ3,ξ4, where ξ1=w1,w2,w3, ξ2=w4, ξ3=w5,w6,w7, and ξ4=w8 is a partition of VMrP4, then the representations of vertices of MrP4 are as follows: rw1|ξ=0,3,1,4, rw2|ξ=0,2,1,3, rw3|ξ=0,1,1,2, rw4|ξ=1,0,2,1, rw5|ξ=1,4,0,3, rw6|ξ=1,3,0,2, rw7|ξ=1,2,0,1, and rw8|ξ=2,1,1,0. It is obvious from the above representations that ξ is a fault-tolerant resolving partition of MrP4.


### 2.2. Fault-Tolerant Partition Dimension of Tortoise Graph

The tortoise graph, denoted byTn, has vertex set VTn=w1,w2,…,wn and edge set ETn=wjwj+1:1≤j≤n−1∪wjwn−j+1:1≤j≤⌊n/2⌋. Tortoise graph T7 is shown in Figure 3.Figure 3
Tortoise graphT7.The following theorems allow us to computepdTn and ℱTn.Theorem 4.
For everyn≥3, where n=2δ+1 and δ≥1, pdTn=3.Proof.
Letξ=ξ1,ξ2,ξ3 be a partition set of VTn for n≥3. rw|ξ with respect to ξ1=wi:1≤i≤n−1/2, ξ2=wn+1/2, and ξ3=wi:n+3/2≤i≤n are as follows:(9)rwϱ|ξ=0,δ−ϱ+1,1,for1≤ϱ≤δ,1,0,1,forϱ=δ+1,1,0,ϱ−δ−1,forδ+2≤ϱ≤n.
It is obvious from the above distinct representations thatξ is resolving partition of Tn; therefore, pdTn≤3. It follows by Proposition 1(b) that pdTn≥3. Hence, pdTn=3.Theorem 5.
For everyn≥3, where n=2δ+1 and δ≥1,(10)ℱTn=3,ifnis3,4,otherwise.Proof.
Letξ=ξ1,ξ2,ξ3 be a partition set of VTn for n=3. Considering ξ1=w1, ξ2=w2, and ξ3=w3, it is easy to see that ξ is fault-tolerant resolving partition of Tn. Now, consider ξ=ξ1,ξ2,ξ3,ξ4 be a partition with 4 partition classes of vertex set of Tn for n=2δ+1, where δ≥2. rw|ξ considering ξ1=wi:1≤i≤n−1/2, ξ2=wi:n+1/2≤i≤n−2, ξ3=wn−1 and ξ4=wn are as follows:(11)rwϱ|ξ=0,2,2,1,forϱ=1,n=5,0,1,1,2,forϱ=2,n=5,0,3,2,1,forϱ=1,n≥7,0,2,1,2,forϱ=2,n≥7,0,1,ϱ−1,ϱ,for3≤ϱ≤δ,1,0,n−ϱ−1,n−ϱ,forδ+1≤ϱ≤n−2,1,1,0,1,forϱ=n−1,1,2,1,0,forϱ=n.
Distinct representations given above show thatξ is fault-tolerant resolving partition of Tn; therefore, ℱTn≤4.
Now, we prove thatℱTn≥4. For this, we show that ℱTn≠3. For contradiction, suppose ξ=ξ1,ξ2,ξ3 be a fault-tolerant partition basis of Tn. One of the partition sets contains at least one vertex of degree 3. Without loss of generality, we assume that wτ is a vertex of degree 3 that belongs to ξ1, and Nwτ=wp,wq,wr. Suppose that ξ1=1, and Nwτ⊆ξ2∪ξ3, Nwτ∩ξ2≥2, or Nwτ∩ξ3≥2. Without loss of generality, we assume at least two vertices f1,f2∈Nwτ∩ξ2. As rf1ξ=1,0,k1 and rf2|ξ=1,0,k2 has two identical coordinates, therefore, it is a contradiction. Now, we consider the following cases when ξ1≥2 and wτ∈ξ1.(1)
Case 1: ifNwτ∩ξ1=wp,wq,wr, then rwτ|ξ=0,b0,c0, rwpξ=0,b1,c1, rwq|ξ=0,b2,c2, and rwr|ξ=0,b3,c3. As b0−1≤b1,b2,b3≤b0+1, so using Pigeonhole principle, there will be similarity in the representation of two vertices at two places, hence a contradiction.(2)
Case 2: ifNwτ∩ξ1=wp,wq and one vertex wr∈ξ2, then rwτ|ξ=0,1,c0, rwp|ξ=0,b1,c1, rwq|ξ=0,b2,c2, and rwr|ξ=1,0,c3. Since 1≤b1,b2≤2, so representation of two vertices will have two identical coordinates, hence a contradiction.(3)
Case 3: ifNwτ∩ξ1=wp and two vertices wq,wr∈ξ2, then rwτ|ξ=0,1,c0, rwp|ξ=0,b1,c1, rwq|ξ=1,0,c2, and rwr|ξ=1,0,c3. Since, representation of two vertices has two identical coordinates, thus, it is a contradiction.(4)
Case 4: ifNwτ∩ξ1=wp, wq∈ξ2 and wr∈ξ3.(1)
Forn=5, Nwp=wτ,s1, Nwq=wτ,wr, and Nwr=wτ,wq,s1. Let s1∈ξ1; then rwτ|ξ=0,1,1, rwp|ξ=0,2,2, and rs1|ξ=0,q1,1, which leads to a contradiction.(2)
Forn≥7, Nwp=wτ,s1,s2, Nwq=wτ,s3, and Nwr=wτ,s2,s3. Let, s1,s2∈ξ1 and s3∈ξ2; then, rwτ|ξ=0,1,1, rwp|ξ=0,2,2, rs1|ξ=0,q1,g1, and rs2|ξ=0,q2,1, which leads to a contradiction. Now, let s1,s2∈ξ1 and s3∈ξ3; then, rwτ|ξ=0,1,1, rwp|ξ=0,2,2, rs1|ξ=0,q1,g1, and rs2|ξ=0,q2,1, which leads to a contradiction.(5)
Case 5: ifNwτ∩ξ1=∅, ξ2 contains at least two neighbours of wτ. Without loss of generality, we suppose that wp,wq∈ξ3; then, rwτ|ξ=0,c0,1, rwp|ξ=1,c1,0, and rwq|ξ=1,c2,0. Again rwp|ξ and rwq|ξ have two identical coordinates; hence, it is a contradiction.
The above discussion follows thatℱTn≥4. Thus, ℱTn=4.Example 3.
Consider the tortoise graphT7, as shown in Figure 3. If ξ=ξ1,ξ2,ξ3,ξ4, where ξ1=w1,w2,w3, ξ2=w4,w5, ξ3=w6, and ξ4=w7 is a partition of VT7, then rw|ξ are as follows: rw1|ξ=0,3,2,1, rw2|ξ=0,2,1,2, rw3|ξ=0,1,2,3, rw4|ξ=1,0,2,3, rw5|ξ=1,0,1,2, rw6|ξ=1,1,0,1, and rw7|ξ=1,2,1,0. The above distinct representations verify that ξ is a fault-tolerant resolving partition of T7.


## 2.1. Fault-Tolerant Partition Dimension of Mirror Graph

Mirror graphMrPn is defined as the disjoint union of graph Ω and its copy Ω´ with additional edges joining each vertex of Ω to its corresponding vertex in Ω´. The set VMrPn=w1,w2,…,w2n and EMrPn=wlwl+1:1≤l≤n−1∪wn+lwn+l+1:1≤l≤n−1∪wlwn+l:1≤l≤n are vertex set and edge set of mirror graph, respectively. Mirror graph MrP4 is shown in Figure 2.Figure 2
Mirror graphMrP4.Yero et al. computed the partition dimension of the mirror graph in the following lemma.Lemma 1 (see [26]).
LetG be the mirror graph MrPn; then, pdMrPn=3.The following theorem allows us to computeℱMrPn.Theorem 3.
For everyn≥2,(7)ℱMrPn=3,ifnis2,4,otherwise.Proof.
Letξ=ξ1,ξ2,ξ3 be a partition set of vertices of MrPn for n=2. Considering ξ1=w1,w2, ξ2=w3, and ξ3=w4, it is easy to observe that ξ is fault-tolerant resolving partition of MrPn.
Now, forn≥3, consider ξ=ξ1,ξ2,ξ3,ξ4 be a partition with 4 partition classes of vertices of MrPn. rw|ξ, considering ξ1=wj:1≤j≤n−1, ξ2=wn, ξ3=wj:n+1≤j≤2n−1, and ξ4=w2n, are as follows:(8)rwϱ|ξ=0,n−ϱ,1,n−ϱ+1for1≤ϱ≤n−1,1,0,2,1forϱ=n,1,0,2n−ϱ+1,2n−ϱforn+1≤ϱ≤2n−1,2,1,1,0forϱ=2n.
As all the above representations are different, soξ is fault-tolerant resolving partition of MrPn; therefore, ℱMrPn≤4.
Now, we prove thatℱMrPn≥4; for this, we show that ℱMrPn≠3. For contradiction, let ξ=ξ1,ξ2,ξ3 be a fault-tolerant partition basis of MrPn. One of the partition sets contains at least one vertex of degree 3. Without loss of generality, we assume that wτ is a vertex of degree 3 that belongs to ξ1, and Nwτ=wp,wq,wr. Suppose that ξ1=1 and Nwτ⊆ξ2∪ξ3, Nwτ∩ξ2≥2, or Nwτ∩ξ3≥2. Without loss of generality, we assume that at least two vertices e1,e2∈Nwτ∩ξ2. As re1|ξ=1,0,k1 and re2|ξ=1,0,k2 have two identical coordinates, so it is a contradiction. Now, we discuss the following cases when ξ1≥2 and wτ∈ξ1.(1)
Case 1: ifNwτ∩ξ1=wp,wq,wr, then rwτ|ξ=0,b0,c0, rwp|ξ=0,b1,c1, rwq|ξ=0,b2,c2, and rwr|ξ=0,b3,c3. As b0−1≤b1,b2,b3≤b0+1, so using Pigeonhole principle, representation of two vertices have two identical coordinates; therefore, it is a contradiction.(2)
Case 2: ifNwτ∩ξ1=wp,wq and one vertex wr∈ξ2, then rwτ|ξ=0,1,c0, rwp|ξ=0,b1,c1, rwq|ξ=0,b2,c2, and rwr|ξ=1,0,c3. Since 1≤b1,b2≤2, so there will be similarity in the representation of two vertices at two places from ξ1 and ξ2; hence, it is a contradiction.(3)
Case 3: ifNwτ∩ξ1=wp and two vertices wq,wr∈ξ2, then rwτ|ξ=0,1,c0, rwp|ξ=0,b1,c1, rwq|ξ=1,0,c2, and rwr|ξ=1,0,c3. Since rwq|ξ and rwr|ξ have two identical coordinates, therefore, it is a contradiction.(4)
Case 4: ifNwτ∩ξ1=wp, wq∈ξ2, and wr∈ξ3, then Nwp=wτ,s1, Nwq=wτ,s1,s2, and Nwr=wτ,s2,s3. Let s1∈ξ1, s2∈ξ2 and s3∈ξ3, then rwτ|ξ=0,1,1 and rs1|ξ=0,1,c1, which leads to a contradiction. Now, let s1∈ξ1, s3∈ξ2, and s2∈ξ3; then, rwτ|ξ=0,1,1 and rs1|ξ=0,1,c1, which leads to a contradiction.(5)
Case 5: ifNwτ∩ξ1=∅ and at least two vertices from Nwτ belong to ξ2, without loss of generality, we suppose that wp,wq∈ξ2; then, rwτ|ξ=0,1,c0, rwp|ξ=1,0,c1, and rwq|ξ=1,0,c2. Again rwp|ξ and rwq|ξ have two identical coordinates, a contradiction.
The above discussions show thatℱMrPn≥4, which completes the proof.Example 2.
Consider the mirror graphMrP4, as shown in Figure 2. If ξ=ξ1,ξ2,ξ3,ξ4, where ξ1=w1,w2,w3, ξ2=w4, ξ3=w5,w6,w7, and ξ4=w8 is a partition of VMrP4, then the representations of vertices of MrP4 are as follows: rw1|ξ=0,3,1,4, rw2|ξ=0,2,1,3, rw3|ξ=0,1,1,2, rw4|ξ=1,0,2,1, rw5|ξ=1,4,0,3, rw6|ξ=1,3,0,2, rw7|ξ=1,2,0,1, and rw8|ξ=2,1,1,0. It is obvious from the above representations that ξ is a fault-tolerant resolving partition of MrP4.


## 2.2. Fault-Tolerant Partition Dimension of Tortoise Graph

The tortoise graph, denoted byTn, has vertex set VTn=w1,w2,…,wn and edge set ETn=wjwj+1:1≤j≤n−1∪wjwn−j+1:1≤j≤⌊n/2⌋. Tortoise graph T7 is shown in Figure 3.Figure 3
Tortoise graphT7.The following theorems allow us to computepdTn and ℱTn.Theorem 4.
For everyn≥3, where n=2δ+1 and δ≥1, pdTn=3.Proof.
Letξ=ξ1,ξ2,ξ3 be a partition set of VTn for n≥3. rw|ξ with respect to ξ1=wi:1≤i≤n−1/2, ξ2=wn+1/2, and ξ3=wi:n+3/2≤i≤n are as follows:(9)rwϱ|ξ=0,δ−ϱ+1,1,for1≤ϱ≤δ,1,0,1,forϱ=δ+1,1,0,ϱ−δ−1,forδ+2≤ϱ≤n.
It is obvious from the above distinct representations thatξ is resolving partition of Tn; therefore, pdTn≤3. It follows by Proposition 1(b) that pdTn≥3. Hence, pdTn=3.Theorem 5.
For everyn≥3, where n=2δ+1 and δ≥1,(10)ℱTn=3,ifnis3,4,otherwise.Proof.
Letξ=ξ1,ξ2,ξ3 be a partition set of VTn for n=3. Considering ξ1=w1, ξ2=w2, and ξ3=w3, it is easy to see that ξ is fault-tolerant resolving partition of Tn. Now, consider ξ=ξ1,ξ2,ξ3,ξ4 be a partition with 4 partition classes of vertex set of Tn for n=2δ+1, where δ≥2. rw|ξ considering ξ1=wi:1≤i≤n−1/2, ξ2=wi:n+1/2≤i≤n−2, ξ3=wn−1 and ξ4=wn are as follows:(11)rwϱ|ξ=0,2,2,1,forϱ=1,n=5,0,1,1,2,forϱ=2,n=5,0,3,2,1,forϱ=1,n≥7,0,2,1,2,forϱ=2,n≥7,0,1,ϱ−1,ϱ,for3≤ϱ≤δ,1,0,n−ϱ−1,n−ϱ,forδ+1≤ϱ≤n−2,1,1,0,1,forϱ=n−1,1,2,1,0,forϱ=n.
Distinct representations given above show thatξ is fault-tolerant resolving partition of Tn; therefore, ℱTn≤4.
Now, we prove thatℱTn≥4. For this, we show that ℱTn≠3. For contradiction, suppose ξ=ξ1,ξ2,ξ3 be a fault-tolerant partition basis of Tn. One of the partition sets contains at least one vertex of degree 3. Without loss of generality, we assume that wτ is a vertex of degree 3 that belongs to ξ1, and Nwτ=wp,wq,wr. Suppose that ξ1=1, and Nwτ⊆ξ2∪ξ3, Nwτ∩ξ2≥2, or Nwτ∩ξ3≥2. Without loss of generality, we assume at least two vertices f1,f2∈Nwτ∩ξ2. As rf1ξ=1,0,k1 and rf2|ξ=1,0,k2 has two identical coordinates, therefore, it is a contradiction. Now, we consider the following cases when ξ1≥2 and wτ∈ξ1.(1)
Case 1: ifNwτ∩ξ1=wp,wq,wr, then rwτ|ξ=0,b0,c0, rwpξ=0,b1,c1, rwq|ξ=0,b2,c2, and rwr|ξ=0,b3,c3. As b0−1≤b1,b2,b3≤b0+1, so using Pigeonhole principle, there will be similarity in the representation of two vertices at two places, hence a contradiction.(2)
Case 2: ifNwτ∩ξ1=wp,wq and one vertex wr∈ξ2, then rwτ|ξ=0,1,c0, rwp|ξ=0,b1,c1, rwq|ξ=0,b2,c2, and rwr|ξ=1,0,c3. Since 1≤b1,b2≤2, so representation of two vertices will have two identical coordinates, hence a contradiction.(3)
Case 3: ifNwτ∩ξ1=wp and two vertices wq,wr∈ξ2, then rwτ|ξ=0,1,c0, rwp|ξ=0,b1,c1, rwq|ξ=1,0,c2, and rwr|ξ=1,0,c3. Since, representation of two vertices has two identical coordinates, thus, it is a contradiction.(4)
Case 4: ifNwτ∩ξ1=wp, wq∈ξ2 and wr∈ξ3.(1)
Forn=5, Nwp=wτ,s1, Nwq=wτ,wr, and Nwr=wτ,wq,s1. Let s1∈ξ1; then rwτ|ξ=0,1,1, rwp|ξ=0,2,2, and rs1|ξ=0,q1,1, which leads to a contradiction.(2)
Forn≥7, Nwp=wτ,s1,s2, Nwq=wτ,s3, and Nwr=wτ,s2,s3. Let, s1,s2∈ξ1 and s3∈ξ2; then, rwτ|ξ=0,1,1, rwp|ξ=0,2,2, rs1|ξ=0,q1,g1, and rs2|ξ=0,q2,1, which leads to a contradiction. Now, let s1,s2∈ξ1 and s3∈ξ3; then, rwτ|ξ=0,1,1, rwp|ξ=0,2,2, rs1|ξ=0,q1,g1, and rs2|ξ=0,q2,1, which leads to a contradiction.(5)
Case 5: ifNwτ∩ξ1=∅, ξ2 contains at least two neighbours of wτ. Without loss of generality, we suppose that wp,wq∈ξ3; then, rwτ|ξ=0,c0,1, rwp|ξ=1,c1,0, and rwq|ξ=1,c2,0. Again rwp|ξ and rwq|ξ have two identical coordinates; hence, it is a contradiction.
The above discussion follows thatℱTn≥4. Thus, ℱTn=4.Example 3.
Consider the tortoise graphT7, as shown in Figure 3. If ξ=ξ1,ξ2,ξ3,ξ4, where ξ1=w1,w2,w3, ξ2=w4,w5, ξ3=w6, and ξ4=w7 is a partition of VT7, then rw|ξ are as follows: rw1|ξ=0,3,2,1, rw2|ξ=0,2,1,2, rw3|ξ=0,1,2,3, rw4|ξ=1,0,2,3, rw5|ξ=1,0,1,2, rw6|ξ=1,1,0,1, and rw7|ξ=1,2,1,0. The above distinct representations verify that ξ is a fault-tolerant resolving partition of T7.


## 3. Conclusion

In this paper, authors conclude thatpdΩ of alternate triangular cycle and tortoise graph for n≥2 is 3. ℱΩ of alternate triangular cycle, mirror graph, and tortoise graph for n≥2 is between 3 and 4. The obtained results led us to the conclusion that the discussed cyclic networks have constant partition and fault-tolerant partition dimension. pdΩ and ℱΩ of these graphs are independent of the number of vertices of the graph. Future research can focus on computing the fault-tolerant partition dimension of alternate square and alternate pentagonal cycle.The significance of the current work can be seen in optimization related to resource management, routing problem, and supply chain problem. These require to group certain nodes in the network to optimally approach the whole network. The least number of grouping required in such scenario can be realised as partition dimension problem. Also, the least number of grouping required to approach the whole network in case of inaccessibility of one of the group relates to fault-tolerant partition dimension of the graph.



---

*Source: 7237168-2021-12-16.xml*