# On Partition Dimension of Some Cycle-Related Graphs

Authors: Changcheng Wei; Muhammad Faisal Nadeem; Hafiz Muhammad Afzal Siddiqui; Muhammad Azeem; Jia-Bao Liu; Adnan Khalil
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

LetG be a simple connected graph. Suppose Δ=Δ1,Δ2,…,Δl an l-partition of VG. A partition representation of a vertex αw.r.tΔ is the l−vector dα,Δ1,dα,Δ2,…,dα,Δl, denoted by rα|Δ. Any partition Δ is referred as resolving partition if ∀αi≠αj∈VG such that rαi|Δ≠rαj|Δ. The smallest integer l is referred as the partition dimension pdG of G if the l-partition Δ is a resolving partition. In this article, we discuss the partition dimension of kayak paddle graph, cycle graph with chord, and a graph generated by chain of cycles. It has been shown that the partition dimension of the said families of graphs is constant.


---

## Body

## 1. Introduction and Preliminaries

The concept of partition dimension is a natural generalization of metric dimension. It was proposed in [1]. This concept came from the study of metric dimension which was defined independently in [2, 3]. This parameter of a graph was proved NP-complete problem given [4]. The metric dimension of a connected graph is based on the distance between vertices, while partition dimension is based on the distance between a vertex and a set containing some vertices. Many researchers worked on this topic. A significant number of papers were published and some of them are given in [5–9]. The problem of finding partition dimension of a connected graph is still unsolved. There are only some lower and upper bounds for the partition dimension of general connected graph available in the literature and the exact values are still open. An upper bound for the partition dimension of a tree is given in [10]. The partition dimension of certain classes of graphs is given in [11–13].Graph theory is very vast field of applied and computational mathematics. That is why most of the applied sciences field extensively uses the graph theory. The partition dimension is also considered an applied topic of graph theory, and some of them are Djokovic–Winkler relation [14], strategies for the mastermind game [15], network discovery and verification [16], and in chemistry to represent the chemical compounds [17, 18]. In digital world, it is used to recognize the pattern, in robotics, it used for image processing, and it also plays a key role for the management of hierarchical data structures [19]. However, the applications of partition are still limited because the computational cost to compute the partition dimension is very complex. Some other applications of this concept is the navigation of robots in networks, and for interest, few areas appear in these literature [2, 20].The partition dimension of a graph can be constant, but some graphs have bounded. Here, are some literature works. Ahmed et al. [21] computed the metric dimension of kayak paddle graph and cycle graph with chords and proved that adding an edge in a cycle graph will not affect the metric dimension of a cycle graph. Mehreen et al. [5] computed the partition dimension of fullerene graph is 3. Rajan et al. [7] described the constant partition dimension of hexagonal and honeycomb networks. Partition dimension of certain honeycomb-derived networks is computed in [6]. The partition dimension of some wheel-related graphs is computed in [22]. Rodrìguez-Velàzquez et al. [8, 9] worked on the trees and unicyclic graphs and computed the bounds on the partition dimension. For more details, we refer to [23–26].The distance between two verticesv1,v2∈VG is a shortest path between them and is denoted by dv1,v2. Let Δ=Δ1,…,Δl be an l-partition of the vertex set VG and rv|Δ=dv,Δ1,dv,Δ2,…,dv,Δa be an l-tuple representing a unique code of v w.r.t to Δ. If all representation codes of the vertex set of the graph G are unique w.r.t to Δ, then Δ is a resolving partition. This partition with the minimum value of l is referred as partition dimension of G and is denoted by pdG.This paper deals with the partition dimension of the kayak paddle graph, a cycle graph with a chord, and a graph generated by a chain of cycles. More precisely, we computed the partition dimension of said families of graphs and it turns out to be constant, i.e., 3.Following theorems are very helpful in finding the partition dimension of a connected graph.Theorem 1.
(see [1]). Let Π be a resolving partition of VG of a graph G and u,v∈VG. If du,w=dv,w for all vertices w∈VG/u,v, then uandv belong to different classes of Π.Theorem 2.
(see [1]). Let G be a simple and connected graph of order n; then,(i)
pdG is 2 iff G is a path graph(ii)
pdG is n iff G is a complete graphThe remaining article is managed as follows. In Section2, the partition dimension of kayak paddle graph is computed, which is constant for all three parameters given in the definition. In Section 3, the partition dimension of cycle graph with chord is discussed, and in Section 4, we study partition dimension of a family of graph generated by chain of cycles. In the end, conclusion and references have been given.


## 2. Kayak Paddle Graph

This section deals with the graph generated by cycle, known as kayak paddle graph, denoted byKPx,y,z. This family of graphs can be constructed by considering two cycles of length x and y and a path of length z with x,y≥3andz≥2. The vertex set and edge set of kayak paddle graph are as follows, respectively:(1)VKPx,y,z=α1,α2,…,αx∪β1,β2,…,βy∪γ1,…,γz−1,EKPx,y,z=αiαi+1:1≤i≤x∪βiβi+1:1≤i≤y∪γiγi+1:1≤i≤z−2∪α1γ1,γz−1β1,where αx+1=α1 and β1=βy+1.Figure1 shows a kayak paddle graph KP12,8,5 with two cycles of length x=12 and y=8 and a path of length z=5 joining them.Figure 1
A kayak paddle graph:KP12,8,5.


### 2.1. Partition Dimension of Kayak Paddle Graph

In the following result, partition dimension of the kayak paddle graph generated by two cycles and a path graph has been discussed.Theorem 3.
LetG=KPx,y,z be a kayak paddle graph with x≥3, y≥4, and z≥2. Then, pdKPx,y,z=3.Proof.
To show thatpdKPx,y,z=3, we use double inequality. First of all, we prove that pdKPx,y,z≤3 by constructing a resolving partition with three elements. For this, consider the following cases on x and y:(i)
Case 1: whenx=2s and y=2t and s,t≥2. We claim Δ=Δ1,Δ2,Δ3 is a resolving set, where Δ1=αs, Δ2=βt, and Δ3=q∈VG|q∉Δ1,Δ2, where q is any of the vertex of the type αi,βi, or γi other than the vertices of Δ1 and Δ2. Then, Table 1 shows different representations of αɛ,βɛ, and γɛ vertices with respect to resolving partition Δ, where a=1 when ɛ=s, b=1 when ɛ=t, and a,b=0, otherwise.(iii)
Case 2: whenx=2s+1, y=2t and t≥2. Then, we split x into the following three subcases:Subcase 2.1: forx=3,5, we claim Δ=Δ1,Δ2,Δ3 is a resolving partition with Δ1=α2, Δ2=βt, and Δ3=q∈VG|q∉Δ1,Δ2. Then, Table 2 shows different representations of αɛ,βɛ, and γɛ with respect to partition Δ, where a=1 when ɛ=2, b=1 when ɛ=t, and a,b=0, otherwise.Subcase 2.2: forx=7, we claim Δ=Δ1,Δ2,Δ3 is a resolving partition with Δ1=α3, Δ2=βt, and Δ3=q∈VG|q∉Δ1,Δ2. Then, Table 3 shows different representations of αɛ,βɛ, and γɛ with respect to the partition Δ, where a=1 when ɛ=3, b=1 when ɛ=t, and a,b=0, otherwise.Subcase 2.3: forx=2s+1 and s≥4, we claim Δ=Δ1,Δ2,Δ3 is a resolving partition Δ1=αs, Δ2=βt, and Δ3=q∈VG|q∉Δ1,Δ2. Then, Table 4 shows different representations of αɛ,βɛ, and γɛ with respect to the partition Δ, where a=1 when ɛ=s, b=1 when ɛ=t, and a,b=0, otherwise.(iv)
Case 3: whenx=2s+1 and y=2t+1, then we split x and y in the following 9 subcases:Subcase 3.1: forx=3 and y=3,5, we claim Δ=Δ1,Δ2,Δ3 is a resolving partition with Δ1=α2, Δ2=β2, and Δ3=q∈VG|q∉Δ1,Δ2. Then, Table 5 shows different representations of αɛ,βɛ, and γɛ with respect to the partition Δ, where a=b=1 when ɛ=2 and a,b=0, otherwise.Subcase 3.2: forx=3 and y=7, we claim Δ=Δ1,Δ2,Δ3 is a resolving partition with Δ1=α2, Δ2=β3, Δ3=q∈VG|q∉Δ1,Δ2. Then, Table 6 shows different representations of αɛ,βɛ, and γɛ with respect to the partition Δ, where a=1 when ɛ=2, b=1 when ɛ=3, and a,b=0, otherwise.Subcase 3.3: forx=3 and y=2t+1 and t≥4, we claim Δ=Δ1,Δ2,Δ3 is a resolving partition, where Δ1=α2, Δ2=βt, and Δ3=q∈VG|q∉Δ1,Δ2. Then, Table 7 shows different representations of αɛ,βɛ, and γɛ with respect to the partition Δ, where a=1 when ɛ=2, b=1 when ɛ=t, and a,b=0, otherwise.Subcase 3.4: forx=5 and y=5 and t≥4, we claim Δ=Δ1,Δ2,Δ3 is a resolving partition, where Δ1=α2, Δ2=β2, and Δ3=q∈VG|q∉Δ1,Δ2. Then, Table 8 shows different representation of αɛ,βɛ, and γɛ with respect to the partition Δ, where a=b=1 when ɛ=2 and otherwise a,b are 0.Subcase 3.5: forx=5 and y=7 and t≥4, we claim Δ=Δ1,Δ2,Δ3 is a resolving partition, where Δ1=α2, Δ2=β3, and Δ3=q∈VG|q∉Δ1,Δ2. Then, Table 9 shows different representation of αɛ,βɛ, and γɛ with respect to the partition Δ, where a=1 when ɛ=2, b=1 when ɛ=3, and a,b=0, otherwise.Subcase 3.6: forx=5 and y=2t+1 and t≥4, we claim Δ=Δ1,Δ2,Δ3 is a resolving partition, where Δ1=α2, Δ2=βt, and Δ3=q∈VG|q∉Δ1,Δ2. Then, Table 10 shows different representation of αɛ,βɛ, and γɛ with respect to the partition Δ, where a=1 when ɛ=2, b=1 when ɛ=t, and a,b=0, otherwise.Subcase 3.7: forx=7 and y=7, we claim Δ=Δ1,Δ2,Δ3 is a resolving partition, where Δ1=α3, Δ2=β3, and Δ3=q∈VG|q∉Δ1,Δ2. Then, Table 11 shows different representations of αɛ,βɛ, and γɛ with respect to the partition Δ, where a=b=1 when ɛ=3 and a,b=0, otherwise.Subcase 3.8: forx=7 and y=2t+1 and t≥4, we claim Δ=Δ1,Δ2,Δ3 is a resolving with Δ1=α3, Δ2=βt, and Δ3=q∈VG|q∉Δ1,Δ2. Then, Table 12 shows different representations of αɛ,βɛ, and γɛ with respect to the partition Δ, where a=1 when ɛ=3, b=1 when ɛ=t, and a,b=0, otherwise.Subcase 3.9: forx=2s+1 and y=2t+1 and s,t≥4, we claim Δ=Δ1,Δ2,Δ3 is a resolving 3-partition with Δ1=αs, Δ2=βt, and Δ3=q∈VG|q∉Δ1,Δ2. Then, Table 13 shows different representation of αɛ,βɛ, and γɛ with respect to the partition Δ, where a=1 when ɛ=s, b=1 when ɛ=t, and a,b=0, otherwise.
Since all the verticesαɛ, βɛ, and γɛ have different representations with respect to the partition Δ, we obtain(2)pdKPx,y,z≤3.
Conversely. To prove that pdKPx,y,z≥3, suppose, on contrary, pdKPx,y,z=2. It is not possible because pdG=2 if and only G is a path graph. Our assumption is wrong. Therefore,(3)pdKPx,y,z≥3.
Hence, from inequalities (2) and (3), we conclude that(4)pdKPx,y,z=3.Table 1
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:1≤ɛ≤ss−ɛt+z−2+ɛaαɛ:s+1≤ɛ≤xɛ−s2s+t+z−ɛ0βɛ:1≤ɛ≤ts+z−2+ɛt−ɛbβɛ:t+1≤ɛ≤x2t+s+z−ɛɛ−t0γɛ:1≤ɛ≤z−1s+ɛ−1t−ɛ+z−10Table 2
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:ɛ=1,22−ɛt+z−2+ɛaαɛ:ɛ=x=31t+z0αɛ:ɛ=3,4,x=5ɛ−2t+z+10αɛ:ɛ=x=52t+z0βɛ:1≤ɛ≤tz+ɛt−ɛbβɛ:t+1≤ɛ≤y2t+2+z−ɛɛ−t0γɛ:1≤ɛ≤z−11+ɛt−ɛ+z−10Table 3
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:ɛ=1,2,33−ɛt+z−2+ɛaαɛ:ɛ=4,5ɛ−3t+z+20αɛ:ɛ=6,73t+z−ɛ+70βɛ:1≤ɛ≤tz+ɛ+1t−ɛbβɛ:t+1≤ɛ≤y2t+z−ɛ+3ɛ−t0γɛ:1≤ɛ≤z−1ɛ+2t−ɛ+z−10Table 4
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:1≤ɛ≤ss−ɛt+z−2+ɛaαɛ:ɛ=s+1,s+2ɛ−ss+t+z−10αɛ:s+3≤ɛ≤2s−1ɛ−s2s+t+z−ɛ+10αɛ:2s≤ɛ≤xs2s+t+z−ɛ+10βɛ:1≤ɛ≤ts+z+ɛ−2t−ɛbβɛ:t+1≤ɛ≤y2t+s+z−ɛɛ−t0γɛ:1≤ɛ≤z−1ɛ+s−1t−ɛ+z−10Table 5
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:ɛ=1,22−ɛz+ɛaαɛ:ɛ=31z+20βɛ:ɛ=1,2z+ɛ2−ɛbβɛ:ɛ=y=3z+210βɛ:ɛ=3,4,y=5z+3ɛ−20βɛ:ɛ=y=5z+220γɛ:1≤ɛ≤z−1ɛ+11−ɛ+z0Table 6
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:ɛ=1,22−ɛz+ɛ+1aαɛ:ɛ=31z+30βɛ:ɛ=1,2,3z+ɛ3−ɛbβɛ:ɛ=4,5z+4ɛ−30βɛ:ɛ=6,7z+9−ɛ30γɛ:1≤ɛ≤z−1ɛ+12−ɛ+z0Table 7
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:ɛ=1,22−ɛt+z+ɛ−2aαɛ:ɛ=31t+z0βɛ:1≤ɛ≤tz+ɛt−ɛbβɛ:ɛ=t+1,t+2t+z+1ɛ−t0βɛ:t+3≤ɛ≤2t−12t+z−ɛ+3ɛ−t0βɛ:2t≤ɛ≤y2t+z−ɛ+3t0γɛ:1≤ɛ≤z−11+ɛt−ɛ+z−10Table 8
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:ɛ=1,22−ɛz+ɛaαɛ:ɛ=3,4ɛ−1z+30αɛ:ɛ=52z+20βɛ:ɛ=1,2z+ɛ2−ɛbβɛ:ɛ=3,4z+3ɛ−20βɛ:ɛ=52+z20γɛ:1≤ɛ≤z−11+ɛz−ɛ+10Table 9
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:ɛ=1,22−ɛz+ɛ+1aαɛ:ɛ=3,4ɛ−1z+40αɛ:ɛ=52z+30βɛ:ɛ=1,2,3z+ɛ3−ɛbβɛ:ɛ=4,5z+4ɛ−30βɛ:ɛ=5z+9−ɛ30γɛ:1≤ɛ≤z−11+ɛz−ɛ+20Table 10
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:ɛ=1,22−ɛt+z+ɛ−2aαɛ:ɛ=3,4ɛ−1t+z+10αɛ:ɛ=52z+t0βɛ:1≤ɛ≤tz+ɛt−ɛbβɛ:ɛ=t+1,t+2t+z+1ɛ−t0βɛ:t+3≤ɛ≤2t−12t+z−ɛ+3t0γɛ:1≤ɛ≤z−11+ɛz−ɛ+10Table 11
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:ɛ=1,2,33−ɛz+ɛ+1aαɛ:ɛ=4,5ɛ−3z+50αɛ:ɛ=6,73z+10−ɛ0βɛ:ɛ=1,2,3z+1+ɛ3−ɛbβɛ:ɛ=4,5z+5ɛ−30βɛ:ɛ=6,7z+10−ɛ30γɛ:1≤ɛ≤z−12+ɛz−ɛ+20Table 12
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:ɛ=1,2,33−ɛt+z+ɛ−2aαɛ:ɛ=4,5ɛ−3t+z+20αɛ:ɛ=6,73t+z−ɛ+70βɛ:1≤ɛ≤tz+1+ɛt−ɛbβɛ:ɛ=t+1,t+2t+z+2ɛ−t0βɛ:t+3≤ɛ≤2t−12t+z−ɛ+4ɛ−t0βɛ:2t≤ɛ≤y2t+z−ɛ+4t0γɛ:1≤ɛ≤z−12+ɛt+z−ɛ−10Table 13
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:1≤ɛ≤ss−ɛt+z+ɛ−2aαɛ:ɛ=s+1,s+2ɛ−st+s+z−10αɛ:s+3≤ɛ≤2s−1ɛ−s2s+t+z−ɛ+10αɛ:2s≤ɛ≤xs2s+t+z−ɛ+10βɛ:1≤ɛ≤ts+z−1+ɛt−ɛbβɛ:ɛ=t+1,t+2s+2t+z−ɛ+1ɛ−t0βɛ:t+3≤ɛ≤2t−1s+2t+z−ɛ+1ɛ−t0βɛ:2t≤ɛ≤ys+2t+z−ɛ+1t0γɛ:1≤ɛ≤z−1s−1+ɛt+z−ɛ−10


## 2.1. Partition Dimension of Kayak Paddle Graph

In the following result, partition dimension of the kayak paddle graph generated by two cycles and a path graph has been discussed.Theorem 3.
LetG=KPx,y,z be a kayak paddle graph with x≥3, y≥4, and z≥2. Then, pdKPx,y,z=3.Proof.
To show thatpdKPx,y,z=3, we use double inequality. First of all, we prove that pdKPx,y,z≤3 by constructing a resolving partition with three elements. For this, consider the following cases on x and y:(i)
Case 1: whenx=2s and y=2t and s,t≥2. We claim Δ=Δ1,Δ2,Δ3 is a resolving set, where Δ1=αs, Δ2=βt, and Δ3=q∈VG|q∉Δ1,Δ2, where q is any of the vertex of the type αi,βi, or γi other than the vertices of Δ1 and Δ2. Then, Table 1 shows different representations of αɛ,βɛ, and γɛ vertices with respect to resolving partition Δ, where a=1 when ɛ=s, b=1 when ɛ=t, and a,b=0, otherwise.(iii)
Case 2: whenx=2s+1, y=2t and t≥2. Then, we split x into the following three subcases:Subcase 2.1: forx=3,5, we claim Δ=Δ1,Δ2,Δ3 is a resolving partition with Δ1=α2, Δ2=βt, and Δ3=q∈VG|q∉Δ1,Δ2. Then, Table 2 shows different representations of αɛ,βɛ, and γɛ with respect to partition Δ, where a=1 when ɛ=2, b=1 when ɛ=t, and a,b=0, otherwise.Subcase 2.2: forx=7, we claim Δ=Δ1,Δ2,Δ3 is a resolving partition with Δ1=α3, Δ2=βt, and Δ3=q∈VG|q∉Δ1,Δ2. Then, Table 3 shows different representations of αɛ,βɛ, and γɛ with respect to the partition Δ, where a=1 when ɛ=3, b=1 when ɛ=t, and a,b=0, otherwise.Subcase 2.3: forx=2s+1 and s≥4, we claim Δ=Δ1,Δ2,Δ3 is a resolving partition Δ1=αs, Δ2=βt, and Δ3=q∈VG|q∉Δ1,Δ2. Then, Table 4 shows different representations of αɛ,βɛ, and γɛ with respect to the partition Δ, where a=1 when ɛ=s, b=1 when ɛ=t, and a,b=0, otherwise.(iv)
Case 3: whenx=2s+1 and y=2t+1, then we split x and y in the following 9 subcases:Subcase 3.1: forx=3 and y=3,5, we claim Δ=Δ1,Δ2,Δ3 is a resolving partition with Δ1=α2, Δ2=β2, and Δ3=q∈VG|q∉Δ1,Δ2. Then, Table 5 shows different representations of αɛ,βɛ, and γɛ with respect to the partition Δ, where a=b=1 when ɛ=2 and a,b=0, otherwise.Subcase 3.2: forx=3 and y=7, we claim Δ=Δ1,Δ2,Δ3 is a resolving partition with Δ1=α2, Δ2=β3, Δ3=q∈VG|q∉Δ1,Δ2. Then, Table 6 shows different representations of αɛ,βɛ, and γɛ with respect to the partition Δ, where a=1 when ɛ=2, b=1 when ɛ=3, and a,b=0, otherwise.Subcase 3.3: forx=3 and y=2t+1 and t≥4, we claim Δ=Δ1,Δ2,Δ3 is a resolving partition, where Δ1=α2, Δ2=βt, and Δ3=q∈VG|q∉Δ1,Δ2. Then, Table 7 shows different representations of αɛ,βɛ, and γɛ with respect to the partition Δ, where a=1 when ɛ=2, b=1 when ɛ=t, and a,b=0, otherwise.Subcase 3.4: forx=5 and y=5 and t≥4, we claim Δ=Δ1,Δ2,Δ3 is a resolving partition, where Δ1=α2, Δ2=β2, and Δ3=q∈VG|q∉Δ1,Δ2. Then, Table 8 shows different representation of αɛ,βɛ, and γɛ with respect to the partition Δ, where a=b=1 when ɛ=2 and otherwise a,b are 0.Subcase 3.5: forx=5 and y=7 and t≥4, we claim Δ=Δ1,Δ2,Δ3 is a resolving partition, where Δ1=α2, Δ2=β3, and Δ3=q∈VG|q∉Δ1,Δ2. Then, Table 9 shows different representation of αɛ,βɛ, and γɛ with respect to the partition Δ, where a=1 when ɛ=2, b=1 when ɛ=3, and a,b=0, otherwise.Subcase 3.6: forx=5 and y=2t+1 and t≥4, we claim Δ=Δ1,Δ2,Δ3 is a resolving partition, where Δ1=α2, Δ2=βt, and Δ3=q∈VG|q∉Δ1,Δ2. Then, Table 10 shows different representation of αɛ,βɛ, and γɛ with respect to the partition Δ, where a=1 when ɛ=2, b=1 when ɛ=t, and a,b=0, otherwise.Subcase 3.7: forx=7 and y=7, we claim Δ=Δ1,Δ2,Δ3 is a resolving partition, where Δ1=α3, Δ2=β3, and Δ3=q∈VG|q∉Δ1,Δ2. Then, Table 11 shows different representations of αɛ,βɛ, and γɛ with respect to the partition Δ, where a=b=1 when ɛ=3 and a,b=0, otherwise.Subcase 3.8: forx=7 and y=2t+1 and t≥4, we claim Δ=Δ1,Δ2,Δ3 is a resolving with Δ1=α3, Δ2=βt, and Δ3=q∈VG|q∉Δ1,Δ2. Then, Table 12 shows different representations of αɛ,βɛ, and γɛ with respect to the partition Δ, where a=1 when ɛ=3, b=1 when ɛ=t, and a,b=0, otherwise.Subcase 3.9: forx=2s+1 and y=2t+1 and s,t≥4, we claim Δ=Δ1,Δ2,Δ3 is a resolving 3-partition with Δ1=αs, Δ2=βt, and Δ3=q∈VG|q∉Δ1,Δ2. Then, Table 13 shows different representation of αɛ,βɛ, and γɛ with respect to the partition Δ, where a=1 when ɛ=s, b=1 when ɛ=t, and a,b=0, otherwise.
Since all the verticesαɛ, βɛ, and γɛ have different representations with respect to the partition Δ, we obtain(2)pdKPx,y,z≤3.
Conversely. To prove that pdKPx,y,z≥3, suppose, on contrary, pdKPx,y,z=2. It is not possible because pdG=2 if and only G is a path graph. Our assumption is wrong. Therefore,(3)pdKPx,y,z≥3.
Hence, from inequalities (2) and (3), we conclude that(4)pdKPx,y,z=3.Table 1
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:1≤ɛ≤ss−ɛt+z−2+ɛaαɛ:s+1≤ɛ≤xɛ−s2s+t+z−ɛ0βɛ:1≤ɛ≤ts+z−2+ɛt−ɛbβɛ:t+1≤ɛ≤x2t+s+z−ɛɛ−t0γɛ:1≤ɛ≤z−1s+ɛ−1t−ɛ+z−10Table 2
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:ɛ=1,22−ɛt+z−2+ɛaαɛ:ɛ=x=31t+z0αɛ:ɛ=3,4,x=5ɛ−2t+z+10αɛ:ɛ=x=52t+z0βɛ:1≤ɛ≤tz+ɛt−ɛbβɛ:t+1≤ɛ≤y2t+2+z−ɛɛ−t0γɛ:1≤ɛ≤z−11+ɛt−ɛ+z−10Table 3
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:ɛ=1,2,33−ɛt+z−2+ɛaαɛ:ɛ=4,5ɛ−3t+z+20αɛ:ɛ=6,73t+z−ɛ+70βɛ:1≤ɛ≤tz+ɛ+1t−ɛbβɛ:t+1≤ɛ≤y2t+z−ɛ+3ɛ−t0γɛ:1≤ɛ≤z−1ɛ+2t−ɛ+z−10Table 4
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:1≤ɛ≤ss−ɛt+z−2+ɛaαɛ:ɛ=s+1,s+2ɛ−ss+t+z−10αɛ:s+3≤ɛ≤2s−1ɛ−s2s+t+z−ɛ+10αɛ:2s≤ɛ≤xs2s+t+z−ɛ+10βɛ:1≤ɛ≤ts+z+ɛ−2t−ɛbβɛ:t+1≤ɛ≤y2t+s+z−ɛɛ−t0γɛ:1≤ɛ≤z−1ɛ+s−1t−ɛ+z−10Table 5
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:ɛ=1,22−ɛz+ɛaαɛ:ɛ=31z+20βɛ:ɛ=1,2z+ɛ2−ɛbβɛ:ɛ=y=3z+210βɛ:ɛ=3,4,y=5z+3ɛ−20βɛ:ɛ=y=5z+220γɛ:1≤ɛ≤z−1ɛ+11−ɛ+z0Table 6
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:ɛ=1,22−ɛz+ɛ+1aαɛ:ɛ=31z+30βɛ:ɛ=1,2,3z+ɛ3−ɛbβɛ:ɛ=4,5z+4ɛ−30βɛ:ɛ=6,7z+9−ɛ30γɛ:1≤ɛ≤z−1ɛ+12−ɛ+z0Table 7
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:ɛ=1,22−ɛt+z+ɛ−2aαɛ:ɛ=31t+z0βɛ:1≤ɛ≤tz+ɛt−ɛbβɛ:ɛ=t+1,t+2t+z+1ɛ−t0βɛ:t+3≤ɛ≤2t−12t+z−ɛ+3ɛ−t0βɛ:2t≤ɛ≤y2t+z−ɛ+3t0γɛ:1≤ɛ≤z−11+ɛt−ɛ+z−10Table 8
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:ɛ=1,22−ɛz+ɛaαɛ:ɛ=3,4ɛ−1z+30αɛ:ɛ=52z+20βɛ:ɛ=1,2z+ɛ2−ɛbβɛ:ɛ=3,4z+3ɛ−20βɛ:ɛ=52+z20γɛ:1≤ɛ≤z−11+ɛz−ɛ+10Table 9
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:ɛ=1,22−ɛz+ɛ+1aαɛ:ɛ=3,4ɛ−1z+40αɛ:ɛ=52z+30βɛ:ɛ=1,2,3z+ɛ3−ɛbβɛ:ɛ=4,5z+4ɛ−30βɛ:ɛ=5z+9−ɛ30γɛ:1≤ɛ≤z−11+ɛz−ɛ+20Table 10
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:ɛ=1,22−ɛt+z+ɛ−2aαɛ:ɛ=3,4ɛ−1t+z+10αɛ:ɛ=52z+t0βɛ:1≤ɛ≤tz+ɛt−ɛbβɛ:ɛ=t+1,t+2t+z+1ɛ−t0βɛ:t+3≤ɛ≤2t−12t+z−ɛ+3t0γɛ:1≤ɛ≤z−11+ɛz−ɛ+10Table 11
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:ɛ=1,2,33−ɛz+ɛ+1aαɛ:ɛ=4,5ɛ−3z+50αɛ:ɛ=6,73z+10−ɛ0βɛ:ɛ=1,2,3z+1+ɛ3−ɛbβɛ:ɛ=4,5z+5ɛ−30βɛ:ɛ=6,7z+10−ɛ30γɛ:1≤ɛ≤z−12+ɛz−ɛ+20Table 12
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:ɛ=1,2,33−ɛt+z+ɛ−2aαɛ:ɛ=4,5ɛ−3t+z+20αɛ:ɛ=6,73t+z−ɛ+70βɛ:1≤ɛ≤tz+1+ɛt−ɛbβɛ:ɛ=t+1,t+2t+z+2ɛ−t0βɛ:t+3≤ɛ≤2t−12t+z−ɛ+4ɛ−t0βɛ:2t≤ɛ≤y2t+z−ɛ+4t0γɛ:1≤ɛ≤z−12+ɛt+z−ɛ−10Table 13
Distance codes for the vertices ofKPx,y,z w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3αɛ:1≤ɛ≤ss−ɛt+z+ɛ−2aαɛ:ɛ=s+1,s+2ɛ−st+s+z−10αɛ:s+3≤ɛ≤2s−1ɛ−s2s+t+z−ɛ+10αɛ:2s≤ɛ≤xs2s+t+z−ɛ+10βɛ:1≤ɛ≤ts+z−1+ɛt−ɛbβɛ:ɛ=t+1,t+2s+2t+z−ɛ+1ɛ−t0βɛ:t+3≤ɛ≤2t−1s+2t+z−ɛ+1ɛ−t0βɛ:2t≤ɛ≤ys+2t+z−ɛ+1t0γɛ:1≤ɛ≤z−1s−1+ɛt+z−ɛ−10


## 3. Partition Dimension of Cycle with Chord Graph

In this section, we consider a cycle with chord graph, denoted byCnm. This graph is constructed by joining any two nonadjacent vertices of the cycle. A graph of cycle with chord with vertex set VCnm=v1,v2,…,vn and ECnm=vivi+1:1≤i≤n∪v1vm+1 is shown in Figure 2. To find the partition dimension of cycle with chord graph Cnm, it suffices to consider t≤⌊n/2⌋ for given value of n.Figure 2
A cycle with chord graphC164.The partition dimension of the cycle with chord graph is given in the following result.Theorem 4.
LetCnm be a cycle with chord graph, n≥4 and 2≤m≤n−2. Then, pdCnm=3.Proof.
To show thatpdCnm=3, first, we will prove pdCnm≤3 by constructing a resolving partition having 3 elements. For this, we split n and m into the following two cases:(i)
Case 1: forn=2t and m=2s, we claim Δ=Δ1,Δ2,Δ3 is a resolving partition with Δ1=vt+s, Δ2=vt+s+1, and Δ3=vɛ∈VG|vɛ∉Δ1,Δ2. Then, Table 14 shows different representations of vɛ with respect to the partition Δ, where a=1 when ɛ=t+sandt+s+1 and 0, otherwise.(iii)
Case 2: whenn=2t+1 and m=2s+1, we claim that Δ=Δ1,Δ2,Δ3 is a resolving partition with Δ1=vt+s+1, Δ2=vt+s+2, and Δ3=vɛ∈VG|vɛ∉Δ1,Δ2. Then, Table 15 shows different representations of vɛ with respect to the partition Δ, where a=1 when ɛ=t+s+1andt+s+2 and 0, otherwise.Case 2.1: whenn=2t and m=2s+1, where a=1 when ɛ=t+s+1andt+s+2 and 0, otherwise. Table 16 shows different representations of vɛ with respect to the partition Δ.Case 2.2: whenn=2t+1 and m=2s, where a=1 when ɛ=t+s+1andt+s+2 and 0, otherwise. Table 17 shows different representations of vɛ with respect to the partition Δ.
Since all the vertices ofCnm have different representations with respect to the partition Δ, therefore,(5)pdCnm≤3.
Conversely. To prove that pdCnm≥3, suppose, on the contrary, pdCnm=2. It is not possible because pdG=2 if and only G is a path graph. Therefore,(6)pdCnm≥3.
Hence, from inequalities (5) and (6), we can conclude that(7)pdCnm=3.Table 14
Distance codes for the vertices ofCnm w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3vɛ:1≤ɛ≤st−s−1+ɛt−s+ɛ−10vɛ:s+1≤ɛ≤t+st+s−ɛt+s−ɛ+1avɛ:t+s+1≤ɛ≤nɛ−t−sɛ−t−s−1aTable 15
Distance codes for the vertices ofCnm w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3vɛ:1≤ɛ≤s+1t−s−1+ɛt−s+ɛ−10vɛ:s+2≤ɛ≤t+s+1t+s−ɛ+1t+s−ɛ+2avɛ:t+s+2≤ɛ≤nɛ−t−s−1ɛ−t−s−2aTable 16
Distance codes for the vertices ofCnm w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3vɛ:1≤ɛ≤s+1t−s−1+ɛt−s+ɛ−20vɛ:s+2≤ɛ≤t+s+1t+s−ɛ+1t+s−ɛ+2avɛ:t+s+2≤ɛ≤nɛ−t−s−1ɛ−t−s−2aTable 17
Distance codes for the vertices ofCnm w.r.t Δ.
d⋅,⋅Δ1Δ2Δ3vɛ:1≤ɛ≤st−s+ɛt−s+ɛ−10vɛ:ɛ=s+1tt0vɛ:s+2≤ɛ≤t+s+1t+s−ɛ+1t+s−ɛ+2avɛ:t+s+2≤ɛ≤nɛ−t−s−1ɛ−t−s−2a


## 4. Cycles’ Chain Graph

This section deals with the graph generated by taking and joiningm copies of cycles and m−1 copies of path of length 1 alternately. This graph is denoted by CCnm with vertex set VG=a1,a2,…,amn and edge set EG=aiai+1:1≤i≤n∪am−1n+iam−1n+i+1:m≥2∪aj−1n+2aj+1n:1≤j≤m−1, where m represents the number of cycles and n represents the number of vertices in a cycle, and for each cycle, amn+1=am−1n+1, i.e., for m=1 and an+1=a1 and for m=2a2n+1=an+1. The order and size of the chain graph is κ=VCCnm=nm and ECCnm=mn+1−1, respectively. Figure 3 shows chain of cycles’ graph CCnm.Figure 3
Chain of cycles’ graphCCnm.


### 4.1. Partition Dimension of Chain of Cycles’ GraphCCnm

In this section, we study the partition dimension of graph generated by chain of cyclesCCnm. The following theorem presents the partition dimension of the graph CCnm.Theorem 5.
Ifn≥5 and m≥2, then pdCCnm=3.Proof.
First, we provepdCCnm≤3 by constructing a resolving partition set Δ=Δ1,Δ2,Δ3Δ1=a1, Δ2=aκ−n+1, and Δ3=ak∈VG|ak∉Δ1,Δ2 from the vertex set of CCnm. We assume the following cases on the vertex set of G=CCnm and on the copies of cycle graph, i.e., m.
Table18 shows different representations of ak with respect to the partition Δ1.
Tables19–21 show different representations of ak with respect to the partition Δ2.
Third vector representations are(8)rak|Δ3=1,k=1,κ−n+1,0,otherwise.
Hence, it follows from the above discussion thatpdCCnm≤3 because all the vertices of CCnm have unique representations with respect to resolving partition set Δ.
The reverse inequalitypdCCnm≥3 can be easily followed from the fact that partition dimension of the graph G is 2 if and only if G is a path graph. Thus, we conclude that, for n≥5 and m≥2,(9)pdCCnm=3.Table 18
Distance codes forak w.r.t Δ1.
d⋅,⋅Δ1ak:k=1,2,3,…,⌈n+1/2⌉k−1ak:k=⌈n+1/2⌉+1,⌈n+1/2⌉+2,…,nn−k+1ak:k≡1,2,3,…,⌊n−1/2⌋modn and k≥n+13⌊k/n⌋+k−1−n⌊k/n⌋ak:k≡0,⌊n−1/2⌋+1,⌊n−1/2⌋+2,…,n−1modn and n+1≤k≤2nn⌊k/n⌋+2−kak:k≡0,⌊n−1/2⌋+1,⌊n−1/2⌋+2,…,n−1modn and k>2nn⌊k+⌊n−1/2⌋+1/n⌋−k+2+3⌊k+⌊n−1/2⌋+1/n⌋−2Table 19
Distance codes forak w.r.t Δ2, m=2.
d⋅,⋅Δ1ak:k=13ak:k=2,3,…,⌊n+2/2⌋kak:k=⌊n+2/2⌋+1,…,nn−k+4Table 20
Distance codes forak w.r.t Δ2, m≥3.
d⋅,⋅Δ2ak:k=13⌊nm−1+1/n⌋−1+kak:k=2,3,…,⌊n+2/2⌋3⌊k/n⌋−1+kak:k=⌊n+2/2⌋+1,…,n and k≥n+1n−k+4+3⌊nm−1+1/n⌋−1Table 21
Distance codes forak w.r.t Δ2, m≥2.
d⋅,⋅Δ2ak:k=nm−1+1,nm−1+2,…,nm−1+⌊n/2⌋k−nm−1−1ak:k=nm−1+⌊n/2⌋+1,nm−1+⌊n/2⌋+2,…,nmnm−k+1ak:k≡2,3,…,⌊n+2/2⌋modn and n+1≤k≤nm−13m−⌊k−1/n⌋−2+k−n⌊k/n⌋ak:k≡0,⌊n+2/2⌋+1,…,n−1modn and n+1≤k≤nm−13m−⌊k−1/n⌋−2+4−k+n⌊k+⌊n+2/2⌋/n⌋ak:k≡1modn and n+1≤k≤nm−13m−⌊k/n⌋−1


## 4.1. Partition Dimension of Chain of Cycles’ GraphCCnm

In this section, we study the partition dimension of graph generated by chain of cyclesCCnm. The following theorem presents the partition dimension of the graph CCnm.Theorem 5.
Ifn≥5 and m≥2, then pdCCnm=3.Proof.
First, we provepdCCnm≤3 by constructing a resolving partition set Δ=Δ1,Δ2,Δ3Δ1=a1, Δ2=aκ−n+1, and Δ3=ak∈VG|ak∉Δ1,Δ2 from the vertex set of CCnm. We assume the following cases on the vertex set of G=CCnm and on the copies of cycle graph, i.e., m.
Table18 shows different representations of ak with respect to the partition Δ1.
Tables19–21 show different representations of ak with respect to the partition Δ2.
Third vector representations are(8)rak|Δ3=1,k=1,κ−n+1,0,otherwise.
Hence, it follows from the above discussion thatpdCCnm≤3 because all the vertices of CCnm have unique representations with respect to resolving partition set Δ.
The reverse inequalitypdCCnm≥3 can be easily followed from the fact that partition dimension of the graph G is 2 if and only if G is a path graph. Thus, we conclude that, for n≥5 and m≥2,(9)pdCCnm=3.Table 18
Distance codes forak w.r.t Δ1.
d⋅,⋅Δ1ak:k=1,2,3,…,⌈n+1/2⌉k−1ak:k=⌈n+1/2⌉+1,⌈n+1/2⌉+2,…,nn−k+1ak:k≡1,2,3,…,⌊n−1/2⌋modn and k≥n+13⌊k/n⌋+k−1−n⌊k/n⌋ak:k≡0,⌊n−1/2⌋+1,⌊n−1/2⌋+2,…,n−1modn and n+1≤k≤2nn⌊k/n⌋+2−kak:k≡0,⌊n−1/2⌋+1,⌊n−1/2⌋+2,…,n−1modn and k>2nn⌊k+⌊n−1/2⌋+1/n⌋−k+2+3⌊k+⌊n−1/2⌋+1/n⌋−2Table 19
Distance codes forak w.r.t Δ2, m=2.
d⋅,⋅Δ1ak:k=13ak:k=2,3,…,⌊n+2/2⌋kak:k=⌊n+2/2⌋+1,…,nn−k+4Table 20
Distance codes forak w.r.t Δ2, m≥3.
d⋅,⋅Δ2ak:k=13⌊nm−1+1/n⌋−1+kak:k=2,3,…,⌊n+2/2⌋3⌊k/n⌋−1+kak:k=⌊n+2/2⌋+1,…,n and k≥n+1n−k+4+3⌊nm−1+1/n⌋−1Table 21
Distance codes forak w.r.t Δ2, m≥2.
d⋅,⋅Δ2ak:k=nm−1+1,nm−1+2,…,nm−1+⌊n/2⌋k−nm−1−1ak:k=nm−1+⌊n/2⌋+1,nm−1+⌊n/2⌋+2,…,nmnm−k+1ak:k≡2,3,…,⌊n+2/2⌋modn and n+1≤k≤nm−13m−⌊k−1/n⌋−2+k−n⌊k/n⌋ak:k≡0,⌊n+2/2⌋+1,…,n−1modn and n+1≤k≤nm−13m−⌊k−1/n⌋−2+4−k+n⌊k+⌊n+2/2⌋/n⌋ak:k≡1modn and n+1≤k≤nm−13m−⌊k/n⌋−1


## 5. Conclusion and Discussion

In this paper, we computed partition dimension of cycle-related graph such as paddle graph and cycle graph with chord and chain of cycles’ graph. It has been shown that partition dimension of the aforementioned graph is 3. It was proved that the partition dimension of the cycle graph [1] is 3. We conclude that, by making small or significant changes in the cycle graph, do not affect its partition dimension.



---

*Source: 4046909-2021-03-08.xml*