# On the Bounded Partition Dimension of Some Generalised Graph Structures

Authors: Wajdi Alghamdi; Muhammad Ahsan Asim
Journal: Journal of Mathematics
 (2022)

---

## Abstract

Considerλ to be a connected graph with a vertex set Vλ that may be partitioned into any partition set S. If each vertex in λ has a separate representation with regard to S and is an ordered k partition, then the set with S is a resolving partition of λ.. A partition dimension of λ, represented by pd, is the minimal cardinality of resolving k partitions of Vλ. The partition dimension of various generalised families of graphs, such as the Harary graph, Cayley graph, and Pendent graph, is given as a sharp upper bound in this article.


---

## Body

## 1. Introduction and Preliminaries

Computation is the process of analysing anything using mathematical or logical principles. An algorithm’s implementation is a well-known example of computing. An issue is deemed inherently difficult if solving it requires significant resources regardless of the algorithm used. The problem discussed in this research work has computational cost nondeterministic polynomial time, and therefore, it is called as NP-hard problem in short. The partition dimension is introduced in [1] as a natural generalization of the metric dimension.The concept of resolving set was introduced by the authors of [2] and later introduced by the authors of [3]. In [4], the authors worked on the star partition dimension of the cycle and complete graph by using a comb product. Authors worked on the partition dimension of different classes of circulant graph [5]. The authors worked on the cartesian product of different graphs and wrote a note on the partition dimension [6]. Recently [7, 8], the partition dimensions of the various families of convex polytopes and their types of graphs, such as with pendant edges, have been calculated.The partition dimension is used in a variety of fields, including robot navigation, strategies for the mastermind game, network discovery and verification, pattern recognition, and image processing, the Djokovic-Winkler relation, chemistry for representing, chemical compounds, all of which involve the use of hierarchical data structures [9–17].Literature on partition dimension and its bounds on the specific families of graphs are found in [18, 19]. The antivirus properties of COVID structures are discussed in terms of partition dimension and bounds in [20], novel chemical structures of diamonded structures are discovered in [21] in terms of partition dimension bounds, carbon nanotube, and its partition dimension bounds are described in [22], hexagonal Mobius ladder networks are discussed in terms of bounds on the partition dimension in [23], Harary graphs are found in terms of partition dimension bounds in [24], alpha-boron nanotubes are available in [25], a novel chemical structure is found in terms of metric-based parameters in [26], and different generalised families of graphs are discussed in terms of resolving set and partition dimension in [27–29].Definition 1.
“Letξλ and ηλ be the vertex set and edge set (respectively) of a simple, connected graph λ. The least count of the edges between two vertices x1,x2∈ξλ is called the distance dx1,x2 between x1 and x2.”Definition 2.
“Letρ=ρ1,ρ2,…,ρp be an p-ordered set of ξλ. The distance between a vertex x1∈ξλ and a ρj⊂ξλ is defined as dx1,ρj=miny∈ρjdx1,y,1≤j≤p. A planar graph is one that can be embedded in the plane; i.e., it can be drawn on the plane so that no two edges overlap. Let Q=a1,a2,…,ak ordered set of vertices of λ. A vertex a∈ξλ, the representations denoted by ra|Q, is the p-tuple distances as da,a1,da,a2,…,da,ap. If every vertices have the different representations with respect to Q, then Q is called the resolving set of vertices λ.”Definition 3.
The least number ofp in the resolving set is known as the metric dimension dimλ of λ.Definition 4.
“Letχ be the k-ordered partition set and ra|χ=da,χ1,da,χ2,…,da,χk,da,χk be the k-tuple distance representations of a vertex a to χ. If the representations of a differ with respect to χ, then χ is the resolving partition set of a graph’s vertex set.”Definition 5.
The partition dimensionpdλ of λ is defined as the smallest count of sections in the resolving partition set of ξλ [1].
Thedimλ and pdλ can be related for any nontrivial connected graph λ in [1](1)pdλ≤dimλ+1.
The theorems that follow are quite useful in determining the partition dimension of a graph.Theorem 1.
(see[1]). “Let χ be a resolving partition of ξλ and x1,x2∈ξλ. If dx1,x3=dx2,x3 for all vertices x3∈ξλ/x1,x2, Then x1,x2 belong to different classes of χ.”Theorem 2.
(see[1]). “Let λ be a simple and connected graph. Then,(i)
pdλ is 2 iff λ is a path graph(ii)
pdλ is n iff λ is a complete graph.”


## 2. Harary GraphHx,y

HararyHx,y is an x-regular graph with order y the vertex set ξHx,y=βζ:ζ=1,2,…,y, if x is even, then x=2μ≤y−1 for some integer μ≤y−1/2. For each ζ1≤ζ≤y, we join βζ to βζ+1,βζ+2,…,βζ+μ and to βζ−1,βζ−2.,…,βζ−μ.The arrangement of the vertices is made likeβ1,β2,…,βy developed cycle, and then, its every vertex βζ is attached to the μ-vertices that come right after βζ and the μ vertices that move right away βζ. Here are some limits for the Harary graph’s Hx,y partition dimension.Theorem 3.
With parametric valuesy≥5,y≡0,2,3modx and x=4. Let Hx,y is a generalised Harary graph. Then, the partition dimension of Hx,y is ≤4.Proof.
In order to provepdHx,y≤4, we sorted the proof into the given below categories:Case 1.y≡0mod4,y=4μ,μ≥2∈ℤ+.Suppose you have a resolving partition setχ=χ1,χ2,χ3,χ4 where χ1=β1,χ2=β3,χ3=βy−2,χ4=VHx,y/β1,β3,βy−2, the unique and distinct codes of the whole vertex set of Hx,y with regard to χ are as follows:(2)rβ2x|χ=x,x−1,x−1,0ifx=2,3,…,μ0.2cm;μ,μ,μ,0ifx=μ+10.2cm;2μ−x+1,2μ−x+1,2μ−x+1,0ifx=μ+2,…,2μ0.2cm,rβ2x+1|χ=x,x,x−1,0ifx=2,3,…,μ0.2cm;2μ−x,2μ−x+1,2μ−x+1,0ifx=μ+1,…,2μ−10.2cm.Case 2.y≡2mod4,y=4μ+2,μ∈Z+.Suppose the resolving partition setχ=χ1,χ2,χ3,χ4 where χ1=β1,χ2=β2,χ3=β3,χ4=VHx,y/β1,β2,β3, the unique and distinct codes of the whole vertex set of Hx,y with regard to χ are as follows:(3)rβ2x|χ=x,x−1,x−1,0ifx=2,3,…,μ+10.2cm;2μ−x+2,2μ−x+2,2μ−x+3,0ifx=μ+2,…,2μ+10.2cm,rβ2x+1|χ=x,x,x−1,0ifx=2,3,…,μ0.2cm;μ,μ+1,μ,0ifx=μ+10.2cm;2μ−x+1,2μ−x+2,2μ−x+2,0ifx=μ+2,…,2μ0.2cm.Case 3.y≡3mod4,y=4μ+3,μ∈ℤ+.Suppose the resolving partition setχ=χ1,χ2,χ3,χ4 where χ1=β1,χ2=β2,χ3=β3,χ4=VHx,y/β1,β2,β3, the unique and distinct codes of the whole vertex set of Hx,y with regard to χ are as follows:(4)rβ2x|χ=x,x−1,x−1,0ifx=2,3,…,μ+10.2cm;2μ−x+2,2μ−x+3,2μ−x+3,0ifx=μ+2,…,2μ+10.2cm,rβ2x+1|χ=x,x,x−1,0ifx=2,3,…,μ+10.2cm;2μ−x+2,2μ−x+2,2μ−x+3,0ifμ=μ+2,…,2μ+10.2cm.
There are various representations for the complete vertex set ofHx,y in relation to the resolving partition set χ. Hence,(5)pdHx,y≤4.


## 3. The Partition Dimension of Barycentric Subdivision of Cayley GraphsSCayZn⊕Z2n

The Cayley graphsCayZn⊕Z2,n≥3, is a cubic graph that can be obtained as the Cartesian product of a path on two vertices and cycle on n vertices. The Cayley graphs SCayZn⊕Z2n consist of an outer n-cycle y1,y2,…yn and inner n-cycle x1,x2,…xn and set of n-spokes xμyμ:μ=1,2,…,n with order, size, and faces 2n,3n, and n+2, respectively.The barycentric Cayley graphSCayZn⊕Z2 can be obtained by adding new vertices uμ between xμ and x1+μ,vμ between xμ and yμ, and wμ between yμ and y1+μ, modulo n, which is shown in the Figure 1. Its order and size become 5n and 6n, respectively. The cycles’ arrangements in the graph like, xμ:1≤μ≤n called the inner cycle, yμ:1≤μ≤n∪​wμ:1≤μ≤n named as outer cycle, vμ:1≤μ≤n set of interior vertices.Figure 1
Barycentric subdivision of cayley graphsSCayZn⊕Z2n.Theorem 4.
LetSCayZn⊕Z2n denote the barycentric subdivisions of Cayley graphs. Then, pdCayZn⊕Z2≤4 for every n≥4.Proof.
Case 1. Whenn taken as an even,
For this particular case, we assumen=2ζ,ζ≥2,ζ∈Z+. Let χ=χ1,χ2,χ3χ4 be a resolving partition set where χ1=x1,χ2=x2,χ3=x1+ζ, and χ4=∀VG|∉χ1,χ2,χ3. Representations of all vertices VCayZn⊕Z2/χ1∪​χ2∪​χ3 regarding the resolving partition set χ.
The vertices on the inner cycle are represented as follows:(6)rxμ|χ=2−2+μ,2μ−4,2−2+ζ2+μ,0,if3≤μ≤ζ;4−2+ζ2+μ,4−2+ζμ+4,2−2+μ−2+ζ,0,if2+ζ≤μ≤2ζ,ruμ|χ=1,1,2−1+ζ,0,ifμ=1;2−1+μ,2μ−3,2−2+ζ1+μ,0,if2≤μ≤ζ;2−1+ζ,2−1+ζ,1,0,ifμ=1+ζ;4−2+ζ1+μ,4−2+ζμ+3,2−2+μ−1+ζ,0,if2+ζ≤μ≤2ζ.
The internal cycle vertices are represented as follows:(7)rvμ|χ=1,3,21+ζ,0,ifμ=1;2−1+μ,2μ−3,2−2+ζμ+3,0,if2≤μ≤1+ζ;4−2+ζμ+3,4−2+ζμ+5,2−2+μ−1+ζ,0,if2+ζ≤μ≤2ζ.
The following is vertices’ representations on the outer cycle:(8)ryμ|χ=2,4,22+ζ,0,ifμ=1;2μ,2−2+μ,2−2+ζμ+4,0,if2≤μ≤1+ζ;4−2+ζμ+4,4−2+ζμ+6,2−2+μζ,0,if2+ζ≤μ≤2ζ,rwμ|χ=3,3,21+ζ,0,ifμ=1;21+μ,2−1+μ,2−2+ζμ+3,0,if2≤μ≤ζ;21+ζ,21+ζ,3,0,ifμ=1+ζ;4−2+ζμ+3,4−2+ζμ+5,2−2+μ1+ζ,0,if2+ζ≤μ≤2ζ.
Case 2. Whenn consider as an odd,
For this particular case, we assumen=2ζ+1,ζ≥2,ζ∈Z. Let χ=χ1,χ2,χ3χ4 be a resolving set where χ1=x1,χ2=x2,χ3=u1+ζ, and χ4=∀VG|∉χ1,χ2,χ3. Representations of all vertices VCayZn⊕Z2/χ1∪​χ2∪​χ3 regarding the resolving partition set χ.
The vertices on the inner cycle are represented as follows:(9)rxμ|χ=2−2+μ,2μ−4,2−2+ζμ+3,0,if3≤μ≤1+ζ;2ζ,2ζ,1,0,ifμ=2+ζ;4−2+ζμ+4,4−2+ζμ+6,2−2+μ−3+ζ,0,if3+ζ≤μ≤21+ζ,ruμ|χ=1,1,2ζ,0,ifμ=1;2−1+μ,2μ−3,2−2+ζ2+μ,0,if2≤μ≤ζ;4−2+ζμ+3,4−2+ζμ+5,2−2+μ−2+ζ,0,if2+ζ≤μ≤21+ζ.
The internal cycle vertices are represented as follows:(10)rvμ|χ=1,3,2−2+ζ,0,ifμ=1;2−1+μ,2μ−3,2−2+ζμ+4,0,if2≤μ≤1+ζ;2−3+ζ,2−1+ζ,2,0,ifμ=2+ζ;4−2+ζ1+μ,4−2+ζμ+3,2−2+μ−2+ζ,0,if3+ζ≤μ≤21+ζ;2,3,1+ζ,0,ifμ=21+ζ.
The followings are vertices’ representations on the outer cycle:(11)ryμ|χ=2,4,2−1+ζ,0,ifμ=1;2μ,2−2+μ,2−2+ζμ+5,0,if2≤μ≤1+ζ;2−2+ζ,2ζ,3,0,ifμ=2+ζ;4−2+ζ2+μ,4−2+ζμ+4,2−2+μ−1+ζ,0,if3+ζ≤μ≤21+ζ,rwμ|χ=3,3,2ζ,0,ifμ=1;21+μ,2−1+μ,2−2+ζμ+4,0,if2≤μ≤ζ;2−1+ζ,21+ζ,3,0,ifμ=1+ζ;4−2+ζ1+μ,4−2+ζμ+3,2−2+μζ,0,if2+ζ≤μ≤21+ζ.
With respect to the resolving partition setχ, the complete vertex set of SCayZn⊕Z2n has unique representations.(12)pdSCayZn⊕Z2n≤4.


## 4. The Partition Dimension of Pendent Graphext1G

Theorem 5.
Letext1G denote the Pendent graph. Then, pdext1G≤4 for every n≡0mod4,n≥16.Proof.
Letχ=χ1,χ2,χ3χ4 be a resolving partition set of the graph shown in Figure 2, where χ1=u1,χ2=u7,χ3=v23+ζ, and χ4=∀VG|∉χ1,χ2,χ3. Representations of all vertices Vext1G/χ1∪​χ2∪​χ3 regarding the resolving partition set χ.Case 1. When even vertices(13)rw2μ|χ=3,5,3+ζ,0,ifμ=1;4,4,3+ζ,0,ifμ=2;5,3,2+ζ,0,ifμ=3;2+μ,−1μ,ζ+5−μ,0,if4≤μ≤−1+ζ;2+ζ,−1+ζ,4,0,ifμ=ζ;2+ζ,ζ,2,0,ifμ=1+ζ;1+ζ,1+ζ,2,0,ifμ=2+ζ;ζ,2+ζ,4,0,ifμ=3+ζ;23+ζ−μ,6+2ζ−μ,2+μ−ζ,0,ifζ+4≤μ≤2ζ.Case 2. When odd vertices(14)rw2−1+μ|χ=2,5,2+ζ,0,ifμ=1;3,4,3+ζ,0,ifμ=2;4,3,2+ζ,0,ifμ=3;1+μ,−2+μ,ζ−μ+5,0,if4≤μ≤ζ;2+ζ,−1+ζ,3,0,ifμ=1+ζ;1+ζ,ζ,1,0,ifμ=2+ζ;ζ,1+ζ,3,0,ifμ=3+ζ;2ζ−μ+3,2ζ−μ+6,−1+μ+ζ,0,ifζ+4≤μ≤2ζ.
With respect to the resolving partition setχ, the complete vertex set of ext1G has unique representations. Hence,(15)pdext1G≤4.Figure 2
Pendent graphext1G for n=20.Theorem 6.
Letext1G denote the Pendent graph. Then, pdext1G≤5 for every n≡1mod4n≥17.Proof.
Letχ=χ1,χ2,χ3,χ4,χ5 be a resolving partition set where χ1=u1,χ2=u2,χ3=u7,χ4=v21+ζ, and χ5=∀VG|∉χ1,χ2,χ3,χ4. Representations of all vertices Vext1G/χ1∪​χ2∪​χ3∪​χ4 regarding the resolving partition set χ. The representations when n=13 are shown in Tables 1–3.Case 1. When even vertices(16)rw2μ|χ=3,2,5,3+ζ,0,ifμ=1;4,3,4,2+ζ,0,ifμ=2;5,4,3,1+ζ,0,ifμ=3;2+μ,1+μ,−1+μ,ζ−μ+4,0,if4≤μ≤−1+ζ;2+ζ,1+ζ,−1+ζ,3,0,ifμ=ζ;2+ζ,2+ζ,ζ,1,0,ifμ=1+ζ;1+ζ,2+ζ,1+ζ,3,0,ifμ=2+ζ;ζ,1+ζ,2+ζ,5,0,ifμ=3+ζ;2ζ−μ+3,2ζ−μ+4,2ζ−μ+6,−2+μ+ζ,0,ifζ+4≤μ≤2ζ.Case 2. When odd vertices(17)rw2−1+μ|χ=2,3,5,3+ζ,0,ifμ=1;3,3,4,3+ζ,0,ifμ=2;4,4,3,2+ζ,0,ifμ=3;1+μ,1+μ,−2+μ,ζ−μ+5,0,if4≤μ≤−1+ζ;1+ζ,1+ζ,−2+ζ,4,0,ifμ=ζ;2+ζ,2+ζ,−1+ζ,2,0,ifμ=1+ζ;2+ζ,2+ζ,ζ,2,0,ifμ=2+ζ;1+ζ,1+ζ,1+ζ,4,0,ifμ=3+ζ;ζ,ζ,2+ζ,6,0,ifμ=ζ+4;2ζ−μ+4,2ζ−μ+4,2ζ−μ+7,−2+μ+ζ,0,ifζ+5≤μ≤21+ζ.
Every vertex ofext1Ggains the unique representation with respect to the resolving setχ; hence,(18)pdext1G≤5.Table 1
Representations of the vertices whenn=13 w.r.t χ.
r
w
i
|
χ
χ
1
χ
2
χ
3
χ
4
χ
5
w
1
2
3
6
0
0
w
2
3
2
5
6
0
w
3
3
3
4
6
0
w
4
4
3
4
5
0
w
5
4
4
3
4
0
w
6
5
4
3
3
0
w
7
5
5
2
2
0
w
8
5
5
3
1
0
w
9
5
5
3
2
0
w
10
4
5
4
3
0
w
11
4
4
4
4
0
w
12
2
3
4
4
0
w
13
3
3
5
6
0Table 2
Representations of the vertices whenn=13 w.r.t χ.
r
w
i
|
χ
χ
1
χ
2
χ
3
χ
4
w
1
2
4
7
0
w
2
3
3
7
0
w
3
3
3
8
0
w
4
4
2
7
0
w
5
4
3
7
0
w
6
5
3
6
0
w
7
5
4
6
0
w
8
6
4
5
0
w
9
6
5
4
0
w
10
7
5
3
0
w
11
6
6
2
0
w
12
6
6
1
0
w
13
5
7
2
0
w
14
5
6
3
0
w
15
4
6
4
0
w
16
4
5
5
0
w
17
3
5
6
0
w
18
3
4
6
0Table 3
Representations of the vertices whenn=13 with regards to χ.
r
w
i
|
χ
χ
1
χ
2
χ
3
χ
4
w
1
2
4
6
0
w
2
3
3
6
0
w
3
3
3
5
0
w
4
4
2
4
0
w
5
4
3
3
0
w
6
5
3
2
0
w
7
5
4
1
0
w
8
4
4
2
0
w
9
4
5
3
0
w
10
3
5
4
0
w
11
3
4
5
0Theorem 7.
Letext1G denote the Pendent graph. Then, pdext1G≤4 for every n≡2mod4n≥18.Proof.
Letχ=χ1,χ2,χ3,χ4 be a resolving partition set where χ1=u1,χ2=u4,χ3=v2ζ+4, and χ4=∀VG|∉χ1,χ2,χ3. Representations of all vertices Vext1G/χ1∪​χ2∪​χ3 regarding the resolving partition set χ.Case 1. When even vertices(19)rw2μ|χ=3,3,3+ζ,0,ifμ=1;2+μ,μ,ζ−μ+5,0,if2≤μ≤ζ;3+ζ,1+ζ,3,0,ifμ=1+ζ;2+ζ,2+ζ,1,0,ifμ=2+ζ;1+ζ,1+ζ,3,0,ifμ=3+ζ;2ζ−μ+4,2ζ−μ+5,−1+μ+ζ,0,ifζ+4≤μ≤21+ζ.Case 2. When odd vertices(20)rw2−1+μ|χ=2,4,3+ζ,0,ifμ=1;3,3,ζ+4,0,ifμ=2;1+μ,μ,ζ−μ+6,0,if3≤μ≤ζ;2+ζ,1+ζ,4,0,ifμ=1+ζ;2+ζ,2+ζ,2,0,ifμ=2+ζ;1+ζ,3+ζ,2,0,ifμ=3+ζ;ζ,2+ζ,4,0,ifμ=ζ+4;2ζ−μ+4,2ζ−μ+6,−1+μ+ζ,0,ifζ+5≤μ≤2ζ.
Every vertex ofext1Ggains the unique representation with respect to the resolving setχ; hence,(21)pdext1G≤4.Theorem 8.
Letext1G denote the Pendent graph. Then, pdext1G≤4 for every n≡3mod4n≥11.Proof.
Letχ=χ1,χ2,χ3,χ4 be a resolving partition set where χ1=u1,χ2=u4,χ3=v23+ζ, and χ4=∀VG|∉χ1,χ2,χ3. Representations of all vertices Vext1G/χ1∪​χ2∪​χ3 regarding the resolving partition set χ.Case 1. When even vertices,(22)rw2μ|χ=3,3,ζ+4,0,ifμ=1;2+μ,μ,ζ−μ+5,0,if2≤μ≤−1+ζ;2+ζ,ζ,4,0,ifμ=ζ;3+ζ,1+ζ,2,0,ifμ=1+ζ;2+ζ,2+ζ,2,0,ifμ=2+ζ;1+ζ,3+ζ,4,0,ifμ=3+ζ;2ζ−μ+4,2ζ−μ+6,−2+μ+ζ,0,ifζ+4≤μ≤21+ζ.Case 2. When odd vertices,(23)rw2−1+μ|χ=2,4,ζ+4,0,ifμ=1;3,3,3+ζ,0,ifμ=2;1+μ,μ,ζ−μ+5,0,if3≤μ≤ζ;2+ζ,1+ζ,3,0,ifμ=1+ζ;3+ζ,2+ζ,1,0,ifμ=2+ζ;2+ζ,3+ζ,3,0,ifμ=3+ζ;2ζ−μ+5,2ζ−μ+6,−1+μ+ζ,0,ifζ+4≤μ≤22+ζ.
Every vertex ofext1Ggains the unique representation with respect to the resolving setχ; hence,(24)pdext1G≤4.


## 5. Conclusion and Discussion

This article investigates the generalised HararyHx,y graph’s partition dimension’s precise boundaries, and we concluded that(25)pdHx,y≤4.For the Barycentric subdivision of Cayley GraphsSCayZn⊕Z2n,pt(26)pdCayZn⊕Z2≤4.Furthermore, we also discussed the graph named as pendent Graphext1G, and this also gave the same bounds of partition dimension which is(27)pdext1G≤4.We proved all the chosen graphs have upper bounds of partition dimension 4.



---

*Source: 9531182-2022-12-05.xml*