# On Fault-Tolerant Partition Dimension of Homogeneous Caterpillar Graphs

Authors: Kamran Azhar; Sohail Zafar; Agha Kashif
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Metric-related parameters in graph theory have several applications in robotics, navigation, and chemical strata. An important such parameter is the partition dimension of graphs that plays an important role in engineering, computer science, and chemistry. In the context of chemical and pharmaceutical engineering, these parameters are used for unique representation of chemical compounds and their structural analysis. The structure of benzenoid hydrocarbon molecules is represented in the form of caterpillar trees and studied for various attributes including UV absorption spectrum, molecular susceptibility, anisotropy, and heat of atomization. Several classes of trees have been studied for partition dimension; however, in this regard, the advanced variant, the fault-tolerant partition dimension, remains to be explored. In this paper, we computed fault-tolerant partition dimension for homogeneous caterpillarsCp;1, Cp;2, and Cp;3 for p≥5, p≥3, and p≥4, respectively, and it is found to be constant. Further numerical examples and an application are furnished to elaborate the accuracy and significance of the work.


---

## Body

## 1. Introduction and Basic Terminologies

Graph theory is a widely excelling branch of mathematics that is used to model and simplify the solution of daily-life problems. Richly engaged area of research now-a-days is the application of mathematics in chemistry. Graph theory provides simple rules to obtain many qualitative predictions about the structure and reactivity of various compounds. In the chemical graph, vertices of the graph correspond to the atoms of the molecule and edges between the vertices correspond to the chemical bonds. The caterpillar graph plays an important role in chemical graph theory for studying the combinatorial and physical properties of benzenoid hydrocarbons. They have promising uses in data reduction, modeling of interactions, computational chemistry, and ordering of graphs [1]. The partition dimension for various classes of trees such as stars, caterpillars, and homogeneous firecrackers have been computed; however, the values of partition dimensions for most kind of trees are still to be solved completely [2, 3]. Among different parameters of graph theory, partition dimension of the graph is a unique and important parameter and has applications in network discovery and verification [4], mastermind games [5], and image processing [6].In 2000, the concept of partition dimension of the graph was initiated by Chartrand et al. [7] as another variant of the metric dimension of graphs. The metric dimension of graph was first presented by Slater [8] and later by Harary et al. [9]. Consider Ψ to be a connected graph of order n, where VΨ and EΨ are the set of vertices and edges, respectively. If two vertices w,z∈VΨ, then the length of shortest path between w and z in Ψ is the 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 a closed neighbourhood of z will be denoted by Nz=Nz∪z [10]. Consider μ=z1,z2,…,zt∈VΨ to be an ordered subset of VΨ. The representation of z with respect to μ is t-tuple dz,z1,dz,z2,…,dz,zt, denoted by rz|μ. The subset μ is called a resolving set of Ψ, if representation of z with respect to μ is distinct for all z∈VΨ. The metric dimension of Ψ is defined as minμ:μis resolving set ofΨ and is denoted by βΨ. In 2000, Chartrand et al. [11] observed the application of βΨ in pharmaceutical chemistry. Zehui et al. computed the metric dimension of the families of generalized Petersen graphs in [12]. Hussain et al. studied the metric dimension of 1-pentagonal carbon nanocone networks in [13].In 2008, Hernando et al. [14] initiated the concept of fault-tolerant metric dimension of graphs. The resolving set μ of VΨ is called fault-tolerant if μ,α is also a resolving set for each α∈μ. The fault-tolerant metric dimension of Ψ is the minimum cardinality of fault-tolerant resolving set μ and is denoted by β′Ψ. Raza et al. presented bounds on the fault-tolerant metric dimension of three infinite families of regular graphs [15] and also computed fault-tolerant metric dimension of convex polytopes [16]. Seyedi et al. discussed fault-tolerant metric dimension of circulant graphs in [17].LetΩ=Ω1,Ω2,…,Ωt be a partition with t partition classes of the vertex set of connected graph Ψ. The representation of vertex z with respect to partition set Ω is the t-vector dz,Ω1,dz,Ω2,…,dz,Ωt, denoted by rz|Ω. The partition Ω is called a resolving partition of Ψ if the representation of all vertices in Ψ is different. We define the partition dimension of graph Ψ as minΩ:Ωis resolving partition ofΨ, and it is denoted by pdΨ. In [7], Chartrand et al. characterised the graphs with partition dimension 2 or n. The partition dimensions for various classes of connected graphs have been obtained. For instance, some families of trees were discussed by Fredlina et al. [18] and Rodŕiguez et al. [19]. Amrullah studied the partition dimension problem for a subdivision of a homogeneous firecracker in [2]. Boskoro et al. [20] characterised all graphs of order n≥11, having diameter 2 with partition dimension n−3. Mardhaningsih provided partition dimension of a thorn of the fan graph in [21]. Monica et al. discussed the problem for certain classes of series-parallel graphs [22]. Chu et al. provided the sharp bounds for partition dimension of convex polytopes and flower graphs [23]. Wei et al. studied the partition dimension problem for cycle-related graphs in [24]. Circulant graphs were discussed by Maritz et al. [25]. Firstly, Gary et al. and, later, Khuller et al. mentioned the computational complexity of metric dimension of general graphs [26, 27]. The partition dimension is a graph parameter akin to the concept of metric dimension, so its computation is also more complex.The concept of fault-tolerant version of partition dimension of graphs was initiated by Salman et al. [28]. Let Ω=Ω1,Ω2,…,Ωt be a partition with t partition classes of the vertex set of connected graph Ψ. If for each pair of distinct vertices y,z∈VΨ, ry|Ω and rz|Ω differ by at least two places, then the partition Ω is called fault-tolerant resolving partition of Ψ. The fault-tolerant partition dimension of Ψ is defined as minΩ:Ωis fault−tolerant resolving partition ofΨ and is denoted by ℱΨ. In [29], Imran et al. characterised that ℱΨ of all the graphs of order n is n−1. Recently, Kamran et al. have computed the ℱΨ of tadpole and necklace graphs in [30]. Asim et al. have computed ℱΨ of circulant graphs with a connection set 1,2 in [31]. In this paper, we extend this study by considering homogeneous caterpillars Cp;1, Cp;2, and Cp;3 and show that they have constant fault-tolerant partition dimension. Some basic results on ℱΨ are stated as follows.Salman et al. revealed the following basic results onℱΩ.Proposition 1 (see [32]).
Forn≥2,(a)
pdΩ≤ℱΩ(b)
ℱΩ=n iff Ω≅Kn or Ω≅Kn−eProposition 2 (see [28]).
(a)
Forn≥2, ℱΩ≤β′Ω+1(b)
Forn≥3, 3≤ℱΩ≤n
The remaining part of the article is structured in the following manner: Section2 is devoted for the computation of ℱCp;δ, where Cp;δ is a homogeneous caterpillar. In Section 3, we have concluded the paper by giving future research direction and application showing significance of the current work.


## 2. Fault-Tolerant Partition Dimension of the Homogeneous Caterpillar Graph

A caterpillar graph is a tree having a central path withp vertices c1,c2,…,cp. Leaves δ are pendent vertices those are attached to every vertex of the central path. If an equal number of leaf vertices are attached to each ci where 1≤i≤p, then caterpillar is called the homogeneous caterpillar and is denoted by Cp;δ. The set VCp;δ=C∪Aij, where C=ci:1≤i≤p and Aij=aij:1≤i≤p,1≤j≤δ, and ECp;δ=cici+1:1≤i≤p−1∪ciaij:1≤i≤p,1≤j≤δ are the vertex set and edge set of homogeneous caterpillar Cp;δ, respectively. The graph of homogeneous caterpillar C5;3 is shown in Figure 1.Figure 1
Homogeneous caterpillarC5;3.Lemma 1 (see [18]).
LetCp;δ be a homogeneous caterpillar with p,δ≥1. Then, pdCp;δ=3 if and only if (δ=1 and p≥3) or (δ=2 and p≥2) or (δ=3 and p≤3).Lemma 2 (see [3]).
LetCp;δ be a homogeneous caterpillar with any integers p,δ≥1. Then, pdCp;δ=4 if and only if (δ=3 and p≥4) or (δ=4 and p≤4).
The following theorems will allow us to computeℱCp;δ.Theorem 1.
LetCp;δ be a homogeneous caterpillar. If δ=1 and 2≤p≤4, then ℱCp;1=3.Proof.
LetΩ=Ω1,Ω2,Ω3 be a partition with 3 partition classes of the vertices of Cp;1. We have the following:Case (i): forp=2Therv|Ω of C2;1 with respect to Ω1=c1,c2, Ω2=a11, and Ω3=a21 is as follows:(1)rcσ|Ω=0,1,2,forσ=1,0,2,1,forσ=2,raσ1|Ω=1,0,3,forσ=1,1,3,0,forσ=2.Case (ii): forp=3.ConsiderΩ1=c1,c2,a11, Ω2=c3,a31 and Ω3=a21. The rv|Ω of C3;1 is as follows:(2)rcσ|Ω=0,2,2,forσ=1,0,1,1,forσ=2,1,0,2,forσ=3,raσ1|Ω=0,3,3,forσ=1,1,2,0,forσ=2,2,0,3,forσ=3.Case (iii): forp=4ConsiderΩ1=c1,c2,a11, Ω2=c3,c4,a41, and Ω3=a21,a31. The rv|Ω of C4;1 is as follows:(3)rcσ|Ω=0,2,2,forσ=1,0,1,1,forσ=2,1,0,1,forσ=3,2,0,2,forσ=4,raσ1|Ω=0,3,3,forσ=1,1,2,0,forσ=2,2,1,0,forσ=3,3,0,3,forσ=4.
As all the vertices have distinct representations,Ω is fault-tolerant resolving partition of Cp;1; therefore, ℱCp;1≤3. It follows from Proposition 1 (a) and Lemma 1 that ℱCp;1=3, which completes the proof.Theorem 2.
LetCp;δ be a homogeneous caterpillar; if δ=1 and p≥5, or δ=2 and p≥3, then ℱCp;δ≥4.Proof.
In order to prove thatℱCp;δ≥4, we show that ℱCp;δ≠3. Suppose on contrary that Ω=Ω1,Ω2,Ω3 is a fault-tolerant partition basis of Cp;δ. One of the partition sets Ω1,Ω2, or Ω3 contains at least one vertex of degree 3. Without loss of generality, we assume that v is a vertex of degree 3 that belongs to Ω1, and Nv=z1,z2,z3. Suppose Ω1=1 and Nv⊆Ω2∪Ω3, Nv∩Ω2≥2, or Nv∩Ω3≥2. Without loss of generality, we assume that at least two vertices g,h∈Nv∩Ω2. As rg|Ω=1,0,e1 and rh|Ω=1,0,e2 have two identical coordinates, hence a contradiction. Now, we suppose that Ω1≥2. We discuss the following cases:Case 1: ifNv∩Ω1=z1,z2,z3, then rv|Ω=0,b0,c0, rz1|Ω=0,b1,c1, rz2|Ω=0,b2,c2, and rz3|Ω=0,b3,c3. As b0−1≤b1,b2,b3≤b0+1, by Pigeonhole principle, it is observed that two vertices have two identical coordinates in their representation, which leads to a contradiction.Case 2: ifNv∩Ω1=z1,z2 and one vertex z3∈Ω2, then rv|Ω=0,1,c0, rz1|Ω=0,b1,c1, rz2|Ω=0,b2,c2, and rz3|Ω=1,0,c3. Since 1≤b1,b2≤2, the representation of two vertices will again be identical at two places, which is a contradiction.Case 3: ifNv∩Ω1=z1 and two vertices z2,z3∈Ω2, then rv|Ω=0,1,c0, rz1|Ω=0,b1,c1, rz2|Ω=1,0,c2, and rz3|Ω=1,0,c3. As rz2|Ω and rz3|Ω have two identical coordinates, hence a contradiction.Case 4: ifNv∩Ω1=z1, z2∈Ω2 and z3∈Ω3. We have rv|Ω=0,1,1.Case 4(a): forδ=1 and p≥5ConsiderNz1=v,s1, Nz2=v and Nz3=v,s2,s3. Let s1∈Ω1 and s2,s3∈Ω3; then, rs2|Ω=2,q1,0 and rs3|Ω=2,q2,0, which is a contradiction. Now, if s2,s3∈Ω2, then rs2|Ω=2,0,1 and rs3|Ω=2,0,1, a contradiction.Case 4(b): forδ=2 and p≥3Consider,Nz1=v, Nz2=v, and Nz3=v,s1,s2,s3. Let s1,s2,s3∈Ω3; then, rs1|Ω=2,q1,0, rs2|Ω=2,q2,0, and rs3|Ω=2,q3,0 which leads to a contradiction. Now, let s1,s2∈Ω2 and s3∈Ω3; then rs1|Ω=2,0,1 and rs2|Ω=2,0,1, which leads to a contradiction.Case 5: LetNv∩Ω1=∅ and at least two vertices from Nv belong to Ω2. Without loss of generality, we suppose that z1,z2∈Ω2; then, rv|Ω=0,1,c0, rz1|Ω=1,0,c1, and rz2|Ω=1,0,c2. Again, rz1|Ω and rz2|Ω have two identical coordinates, which leads to a contradiction.
It is obvious from this discussion thatℱCp;δ≥4, which completes the proof.Theorem 3.
LetCp;δ be a homogeneous caterpillar; if δ=1 and p≥5, then ℱCp;1=4.Proof.
LetΩ=Ω1,Ω2,Ω3,Ω4 be a partition set of VCp;1. The rv|Ω of Cp;1, taking Ω1=ci:1≤i≤p∪a11, Ω2=aj1:2≤j≤p−2, Ω3=ap−11, and Ω4=ap1, is as follows:(4)rcσ|Ω=0,2,p−1,p,forσ=1,0,1,p−σ,p−σ+1,for2≤σ≤p−2,0,2,1,2,forσ=p−1,0,3,2,1,forσ=p,raσ1|Ω=0,3,p,p+1,forσ=1,1,0,p+1−σ,p+2−σ,for2≤σ≤p−2,1,3,0,3,forσ=p−1,1,4,3,0,forσ=p.
Distinct representations of vertices ofCp;1 show that Ω is a fault-tolerant resolving partition of Cp;1; therefore, ℱCp;1≤4. Also, by Theorem 2, ℱCp;1≥4, which completes the proof.Theorem 4.
LetCp;δ be a homogeneous caterpillar; if δ=2 and p=2, then ℱC2;2=3.Proof.
LetΩ=Ω1,Ω2,Ω3 be a partition set of VC2;2. The rv|Ω of C2;2, taking Ω1=c1,a11, Ω2=c2,a21, and Ω3=a12,a22, is as follows:(5)rcσ|Ω=0,1,1,forσ=1,1,0,1,forσ=2,raσ1|Ω=0,2,2,forσ=1,2,0,2,forσ=2,raσ2|Ω=1,2,0,forσ=1,2,1,0,forσ=2.
It is obvious from the representations in (5) that Ω is a fault-tolerant resolving partition of C2;2; therefore, ℱC2;2≤3. It follows from Proposition 1 (a) and Lemma 1 that ℱC2;2=3, which completes the proof.Theorem 5.
LetCp;δ be a homogeneous caterpillar; if δ=2 and p≥3, then ℱCp;2=4.Proof.
LetΩ=Ω1,Ω2,Ω3,Ω4 be a partition with 4 partition classes of the vertices of Cp;2. The rv|Ω of Cp;2 with respect to Ω1=ci:1≤i≤p∪a11,ai1:3≤i≤p−1, Ω2=a12,a21, Ω3=ai2:2≤i≤p−1∪ap1, and Ω4=ap2 is as follows:(6)rcσ|Ω=0,1,2,p,forσ=1,0,σ−1,1,p−σ+1,for2≤σ≤p.raσ1|Ω=0,2,3,p+1,forσ=1,1,0,2,p,forσ=2,0,σ,2,p+2−σ,for3≤σ≤p−1,1,p,0,2,forσ=p,raσ2|Ω=1,0,3,p+1,forσ=1,1,σ,0,p+2−σ,for2≤σ≤p−1,1,p,2,0,forσ=p.
As all the representations are distinct,Ω is a fault-tolerant resolving partition of Cp;2; therefore, ℱCp;2≤4. Also, from Theorem 2, ℱCp;2≥4. This completes the proof.Figure 2
Homogeneous caterpillarC5;2.Example 1.
Consider the homogeneous caterpillarC5;2, shown in Figure 2.
LetΩ=Ω1,Ω2,Ω3,Ω4 be a partition with 4 partition classes of the vertices of C5;2. The representation of vertices of C5;2, considering Ω1=ci:1≤i≤5∪a11,a31,a41, Ω2=a12,a21, Ω3=a22,a32,a42,a51, and Ω4=a52, is as follows:(7)rc1|Ω=0,1,2,5,rc2|Ω=0,1,1,4,rc3|Ω=0,2,1,3,rc4|Ω=0,3,1,2,rc5|Ω=0,4,1,1,ra11|Ω=0,1,3,6,ra12|Ω=1,0,3,6,ra21|Ω=1,0,2,5,ra22|Ω=1,2,0,5,ra31|Ω=0,3,2,4,ra32|Ω=1,3,0,4,ra41|Ω=0,4,2,3,ra42|Ω=1,4,0,3,ra51|Ω=1,5,0,2,ra52|Ω=1,5,2,0.
The representations in (7) shows that Ω is a fault-tolerant resolving partition of C5;2.
The following lemma will be used in computingℱCp;3.Lemma 3.
IfCp;3 is a homogeneous caterpillar, then we develop the relations of distances of VCp;3.Proof.
The relations of distances of the verticesC=c1,c2,…,cp and Ai3=ai1,ai2,ai3:where,i∈1,2,…,p of homogeneous caterpillar Cp;3 are given as follows:(a)
da11,a=da12,a=da13,a, for a∈Ai3, where i∈2,3,…,p(b)
daj1,a=daj2,a=daj3,a, for a∈A13, where j∈2,3,…,p(c)
da31,a=da32,a=da33,a, for a∈Aj3, where j∈2,4,5,…,p(d)
daj1,c=daj2,c=daj3,c, for c∈C, where j∈1,2,…,p(e)
da21,b=da22,b=da23,b, for b∈C∪A13(f)
da11,b=da12,b=da13,b, for b∈C∪At3,2≤t≤p(g)
da11,b=da12,b=da13,b, for b∈C∪∪i=2p−1Ai3Theorem 6.
LetCp;δ be a homogeneous caterpillar; if δ=3, then(8)ℱCp;3=4,if2≤p≤3,5,ifp≥4.Proof.
LetΩ=Ω1,Ω2,Ω3,Ω4 be a partition with 4 partition classes of vertices of Cp;3 for p=2 and 3. For p=2, consider Ω1=c1,c2,a11,a21, Ω2=a12,a22, Ω3=a13, and Ω4=a23. For p=3, consider Ω1=c1,c2,c3,a11,a21,a31, Ω2=a12,a22, Ω3=a13,a32, and Ω4=a23,a33. It can be observed easily that Ω is a fault-tolerant resolving partition of Cp;3, for p=2 and 3.
Now, letΩ=Ω1,Ω2,Ω3,Ω4,Ω5 be a partition with 5 partition classes of vertices of Cp;3, for p≥4. Partition representations of the vertices of Cp;3, taking Ω1=ci:1≤i≤p∪ai1:1≤i≤p, Ω2=ai2:1≤i≤p−1, Ω3=ai3:1≤i≤p−1, Ω4=ap2, and Ω5=ap3 are as follows:(9)rcσ|Ω=0,1,1,p−σ+1,p−σ+1,for1≤σ≤p−1,0,2,2,1,1,forσ=p,raσ1|Ω=0,2,2,p−σ+2,p−σ+2,for1≤σ≤p−1,0,3,3,2,2,forσ=p,raσ2|Ω=1,0,2,p−σ+2,p−σ+2,for1≤σ≤p−1,1,3,3,0,2,forσ=p,raσ3|Ω=1,2,0,p−σ+2,p−σ+2,for1≤σ≤p−1,1,3,3,2,0,forσ=p.
Unique representations of (9) show thatΩ is a fault-tolerant resolving partition of Cp;3; therefore, ℱCp;3≤5.
Now, we prove thatℱCp;3≥5, for p≥4. For this, we show that ℱCp;3≠4. Suppose on contrary that ℱCp;3=4. Let Ω=Ω1,Ω2,Ω3,Ω4 be a partition set of VCp;3 for p≥4. We discuss the following cases:Case 1: when two partitioning sets ofΩ are subsets of either Ai3:2≤i≤p or C. At least two vertices from a11,a12, and a13 belong to the remaining two partition sets; then, by Lemma 3 ((a) and (d)), representation of two vertices will have three identical coordinates, hence a contradiction. Now, when two partitioning sets of Ω are subsets of A13 and at least two vertices from a21,a22, and a23 belong to the remaining two partition sets, then by Lemma 3 (b), representation of two vertices will have three identical coordinates, hence a contradiction.Case 2: we discuss cases when two partitioning sets are a subset of union of 2 sets of vertices:Case 2(a): when two partitioning sets ofΩ are subsets of A13∪A23 and at least two vertices from a31,a32, and a33 belong to the remaining two partition sets, then by Lemma 3 (c), representation of two vertices will have three identical coordinates, which is a contradiction. When two partitioning sets of Ω are subsets of either A13∪At3:3≤t≤p and at least two vertices from a21,a22, and a23 belong to the remaining two partition sets, then by Lemma 3 (b), representation of two vertices will have three identical coordinates, which is a contradiction.Case 2(b): when two partitioning sets ofΩ are subsets of either Aq3∪Ar3:2≤q≤p−1,p+1≤r≤p and at least two vertices from a11,a12, and a13 belong to the remaining two partition sets, then by Lemma 3 (a), representation of two vertices will have three identical coordinates, which is a contradiction.Case 2(c): when two partitioning sets ofΩ are subsets of C∪A13 and at least two vertices from a21,a22, and a23 belong to the remaining two partition sets, then by Lemma 3 (e), representation of two vertices will have three identical coordinates, which is a contradiction. Finally, when two partitioning sets of Ω are subsets of either C∪At3:2≤t≤p and at least two vertices from a11,a12, and a13 belong to the remaining two partition sets, then by Lemma 3 (f), representation of two vertices will have three identical coordinates, which is a contradiction.Case 3: now we discuss cases when two partitioning sets are subsets of union of3,4,…,p sets of vertices:Case 3(a): when two partitioning sets ofΩ are subsets of either ∪i=3pAi3, the remaining two partition sets will contain at least two ci,cj∈C. Without loss of generality, we suppose that ci,cj belong to Ω3; then, rci|Ω=1,1,0,s and rcj|Ω=1,1,0,w, which is a contradiction.Case 3(b): when two partitioning sets ofΩ are subsets of either C∪∪i=2p−1Ai3, and if A13∉C∪∪i=2p−1Ai3, at least two vertices from a11,a12, and a13 belong to the remaining two partition sets, then by Lemma 3 (g), representation of two vertices will have three identical coordinates, which is a contradiction. If A13∈C∪∪i=2p−1Ai3, then let Ae3 be a vertex set not contained in C∪∪i=2p−1Ai3. At least two vertices from ae1,ae2, and ae3, belong to the remaining two partition sets. Representation of these two vertices with respect to Ω will have three identical coordinates, which is a contradiction.Case 4: when two partition sets ofΩ are subsets of C∪A13∪A23∪⋯∪Ap3, without loss of generality, we suppose these subsets belong to Ω1 and Ω2:Case 4(a): at least two ofai1,ai2,ai3 belong to one of Ω1 or Ω2. Without loss of generality, we suppose that ai1,ai2∈Ω1 and ai3∈Ω2; then, rai1|Ω=0,b,α,s and rai2|Ω=0,b,α,s, where 1≤b≤2, hence a contradiction.Case 4(b): one of the remaining two partition sets contain at least twoci,cj∈C. Without loss of generality, we suppose that ci,cj belong to Ω3; then, rci|Ω=1,1,0,s and rcj|Ω=1,1,0,w, which is a contradiction.Case 4(c): neither two ofai1,ai2,ai3 where 1≤i≤p belong to the same partition set, nor two of ci,cj belong to Ω3 or Ω4. For 4≤p≤6, at least two vertices in Ω1 will have representations of forms r0,2,2,p, r0,2,q,2, 0,2,r,1, r0,2,1,s, r0,1,2,t, and r0,1,u,2, which leads to a contradiction. For p≥7, at least three vertices ck,cl, and cm belong to Ω1 or Ω2. Without loss of generality, we suppose these vertices belong to Ω1; then, rck|Ω=0,1,1,− or 0,1,−,1, rcl|Ω=0,1,1,− or 0,1,−,1, and rcm|Ω=0,1,1,− or 0,1,−,1. Representation of at least two of ck,cl,andcm will be the same at three places, hence a contradiction.
The above discussion shows thatℱCp;3≥5. This completes the proof.Figure 3
Homogeneous caterpillarC4;3.Example 2.
Consider the homogeneous caterpillarC4;3, shown in Figure 3.
LetΩ=Ω1,Ω2,Ω3,Ω4,Ω5 be a partition with 5 partition classes of the vertices of C4;3. The representations of vertices of C4;3, considering Ω1=ci:1≤i≤4∪a11,a21,a31,a41, Ω2=a12,a22,a32, Ω3=a13,a23,a33, Ω4=a42, and Ω5=a43, are as follows:(10)rc1|Ω=0,1,1,4,4,rc2|Ω=0,1,1,3,3,rc3|Ω=0,1,1,2,2,rc4|Ω=0,2,2,1,1,ra11|Ω=0,2,2,5,5,ra12|Ω=1,0,2,5,5,ra13|Ω=1,2,0,5,5,ra21|Ω=0,2,2,4,4,ra22|Ω=1,0,2,4,4,ra23|Ω=1,2,0,4,4,ra31|Ω=0,2,2,3,3,ra32|Ω=1,0,2,3,3,ra33|Ω=1,2,0,3,3,ra41|Ω=0,3,3,2,2,ra42|Ω=1,3,3,0,2,ra43|Ω=1,3,3,2,0.
The representations in (10) shows that Ω is a fault-tolerant resolving partition of C4;3.


## 3. Conclusion

In this paper, we have computed thatFCp;δ for δ=1,2, and 3 is between 3 and 5. The obtained results led us to the conclusion that the structures of homogeneous caterpillars Cp;1, Cp;2, and Cp;3 have constant fault-tolerant partition dimension for p≥5, p≥3, and p≥4, respectively. Future research can focus on computing the fault-tolerant partition dimension for the classes of homogeneous caterpillar Cp;δ, when δ=4,5, and 6.Here, we include an application of routing optimization problem that shows the significance of the current work. Consider a company that wants to pick passengers from different locations in a certain area using minimum resources and avoiding repeated visits. If locations are considered as nodes and roads connecting them as edges of a graph, then locations can be grouped together that require a single vehicle to pick the passenger. The minimum number of grouping required to represent each location uniquely can be realised as the partition dimension problem of the graph. Also, the minimum number of grouping required to uniquely represent each location even if one of the groups is inaccessible relates to fault-tolerant partition dimension of the graph.



---

*Source: 7282245-2021-11-22.xml*