# Partition Dimension of Generalized Petersen Graph

Authors: Hassan Raza; Jia-Bao Liu; Muhammad Azeem; Muhammad Faisal Nadeem
Journal: Complexity
 (2021)

---

## Abstract

LetG=VG,EG be the connected graph. For any vertex i∈VG and a subset B⊆VG, the distance between i and B is di;B=mindi,j|j∈B. The ordered k-partition of VG is Π=B1,B2,…,Bk. The representation of vertex i with respect to Π is the k-vector, that is, ri|Π=di,B1,di,B2,…,di,Bk. The partition Π is called the resolving (distinguishing) partition if ri|Π≠rj|Π, for all distinct i,j∈VG. The minimum cardinality of the resolving partition is called the partition dimension, denoted as pdG. In this paper, we consider the upper bound for the partition dimension of the generalized Petersen graph in terms of the cardinalities of its partite sets.


---

## Body

## 1. Introduction

The graphs considered are simple, undirected, and without loops. The classical distancedi,j between the two vertices i,jVG is the length of the shortest path between them. For an ordered set R=ℓ1,ℓ2,…,ℓk⊆VG, the ordered k-tuple,(1)ri|R=di,ℓ1,di,ℓ2,…,di,ℓk,is known as metric representation of i with respect to R. When the vertices of the graph G have distinct representation, the set R is termed as the resolving (distinguishing) set which contains minimum number of vertices. The minimum cardinality of such a resolving set is the metric dimension of the G, denoted as dimG. Slater introduced this concept in 1975 [1], after which Melter and Harary independently renamed it the resolving set [2]. In the graph’s theoretical study, this concept is called a metric basis or basis set. The concept of metric dimension does find applications in chemistry [3], else problem concerning pattern recognition and image processing, some involves the utilization of hierarchical data structures [4].For an ordered-partitionΠ=B1,B2,…,Bk⊆VG, the partition representation of the vertex i∈VG with respect to Π is(2)ri|Π=di,B1,di,B2,…,di,Bk,where di;Bh1≤h≤k denotes the distance between the vertex i and Bh, that is,(3)di;Bh=mindi,j|j∈Bh.We can affirm thatΠ is the resolving partition of the graph G if different vertices have unique partition representation, that is, ri|Π≠rj|Π, where i,j∈VG. The partition dimension of the graph G is than the minimum number of resolving partition set in G. It is denoted as pdG. This concept was introduced by Chartrand et al. in 2000 [5].The concept of resolving partition sets and partition dimensions extensively appeared in the literature. For example, the graph with partition dimensionV−3 is discussed [6] and the graph obtained by graph operations and its corresponding partition dimension is studied in [7]. The bounds on the partition dimension for convex polytopes are studied in [8–10] and bounds of partition on the circulant and multipartite discussed in [11, 12]. The partition dimension of chemical structure fullerenes graphs is studied in [13], and on the bounded partition, dimension of the Cartesian product of graphs are studied in [14]. Furthermore, in [15], yielded bounds for the subdivision of different graphs, than in [16] presented the bounds on tree graphs. The bounds of unicyclic graphs in the form of subgraphs are considered in [17]. For more recent literature and results, we refer to see [18–24]. The graph obtained by graph operations and its corresponding partition dimension is considered in [7]. The relation between the metric dimension and partition dimension in a connected graph G is represented as follows.Theorem 1 (see [3]).
For a nontrivial connected graphG,(4)dimG≤pdG+1.Some of the known results are related to the parameter of partition dimension of the graphs.Theorem 2 (see [5]).
LetΠ be a partition resolving set of VG and i,j∈VG. If di,m=dj,m, for all vertices m∈VG\i,j, then i,j belongs to different subsets of G.Theorem 3 (see [5]).
LetG be a simple and connected graph; then,(i)
pdG is two iff G is the only path graph(ii)
pdG is G iff G is a complete graph


## 2. Generalized Petersen GraphPn,k

Generalized Petersen graphPn,k, where n≥3 and 1≤k≤⌊n−1/2⌋, is a graph having the vertex set(5)VPn,k=αj,βj:j=1,2,…,n,and the edge set(6)EPn,k=αjαj+1,βjβj+k,αjβj:j=1,2,…,n.Petersen graph is a cubic graph, and it has three types of edges according to the definition of generalized Petersen graphs; the edges between the verticesαj and αj+1 are called outer edges, the edges produced by the vertices βj and βj+k are called inner edges, and the edges created by αj and βj are called spokes. The vertices αj are called outer vertices and βj are known as the inner vertices. The generalized Petersen graph P12,4 is shown in Figure 1. The study on the resolving set and metric dimension of Petersen and generalized Petersen graphs, and we refer the readers to [25–27]. Motivated by these results on the metric dimension of the generalized Petersen graphs, we study the problem of partition dimension and have shown the sharp upper bound.Figure 1
Generalized Petersen graphP12,4.Letm>0 be the positive integer called the modulus. We can say that two integers x and y are congruent modulo m if y−x is divisible by m. It can be written as follows.x=ymodm⇔x−y=m.k, for some positive integer k. The symbol yMODm denotes the smallest positive integer x.x≡ymodm, where yMODm is the remainder when y is divided by m as many times as possible.The difference betweenMODm and modm is the first one is the equality relation, while the second one is the equivalence relation.In this paper, we employed the equivalence relation because it can have many solutions forx. The partition dimension of the generalized Petersen graph is solved while taking the (mod 4), that is, for n≡0,1,2,3mod4.


## 3. Results on the Generalized Petersen GraphPn,k

In this section, we provide sharp bounds on the partition dimension of the generalized Petersen graphPn,k.In the following section,g=⌊j/2⌋, κ=⌈ℓ/2⌉, and p is 1 if the representation of the vertices belongs to the Π\B4 or B1,B2,B3, otherwise 0.Theorem 4.
LetPn,k is a generalized Petersen graph of order n≥20, when n≡0mod4. Then, pdPn,k≤4.Proof.
Letn=4j, where j≥7∈ℤ+. The proof is exhibited by considering two cases.Case 1.
Whenj is odd.
Assume the partition resolving setΠ=B1,B2,B3,B4, where B1=β1, B2=α3, B3=βn−2, and B4=VPn,k\β1,α3,βn−2. Now, we exhibit the representations of vertices of Pn,k with respect to Π.
The representations of the outer vertices;rα4ℓ+1|Π=ℓ+1,2,ℓ+3,p if ℓ=0,1; rα4ℓ+1|Π=ℓ+1,ℓ+3,ℓ+3,p if ℓ=2,…,g−1; rα4ℓ+1|Π=ℓ+1,ℓ+3,ℓ+2,p if ℓ=g; rα4ℓ+1|Π=j−ℓ+1,j−ℓ+4,,j−ℓ+1,p if ℓ=g+1,…,j−1:(7)rα4ℓ+2|Π=ℓ+2,2ℓ+1,ℓ+2,0,ifℓ=0,1,ℓ+2,ℓ+3,ℓ+1,0,ifℓ=2,…,g−1,ℓ+2,ℓ+3,ℓ+1,0,ifℓ=g,j−ℓ+2,j−ℓ+3,j−ℓ,0,ifℓ=g+1,…,j−1,rα4ℓ+3|Π=ℓ+3,ℓ+2,ℓ+3,0,ifℓ=1,…,g−1,ℓ+3,ℓ+2,ℓ+2,0,ifℓ=g,j−ℓ+2,j−ℓ+2,j−ℓ+1,0,ifℓ=g+1,…,j−1.
Further representation of outer vertices arerα4ℓ+4|Π=3,1,4,p if ℓ=0, rα4ℓ+4|Π=ℓ+3,ℓ+3,ℓ+4,p if ℓ=1,2,…,g−1, rα4ℓ+4|Π=ℓ+2,ℓ+3,ℓ+2,p if ℓ=g, rα4ℓ+4|Π=j−ℓ+1,j−ℓ+3,j−ℓ+1,p if ℓ=g+1,…,j−2, and rα4ℓ+4|Π=2,3,3,p if ℓ=j−1.
The above representations indicate that there exist two no vertices having the exact representation in the outer cycle.
Now, the representations of the inner vertices are shown:(8)rβ4ℓ+1|Π=ℓ,ℓ+2,ℓ+4,p,ifℓ=0,1,…,g−1,ℓ,ℓ+2,ℓ+3,0,ifℓ=g,j−ℓ,j−ℓ+3,j−ℓ+2,0,ifℓ=g+1,…,j−1,rβ4ℓ+2|Π=ℓ+3,ℓ+2,ℓ+1,0,ifℓ=0,1,…,g−1,ℓ+3,ℓ+2,ℓ,0,ifℓ=g,j−ℓ+3,j−ℓ+2,j−ℓ−1,p,ifℓ=g+1,…,j−1,rβ4ℓ+3|Π=ℓ+4,ℓ+1,ℓ+4,p,ifℓ=0,1,…,g−1,ℓ+4,ℓ+1,ℓ+3,p,ifℓ=g,j−ℓ+3,j−ℓ+1,j−ℓ+2,p,ifℓ=g+1,…,j−1,rβ4ℓ+4|Π=ℓ+4,ℓ+2,ℓ+5,p,ifℓ=0,1,…,g−1,ℓ+3,ℓ+2,ℓ+3,p,ifℓ=g,j−ℓ+2,j−ℓ+2,j−ℓ+2,p,ifℓ=g+1,…,j−2,3,3,4,p,ifℓ=j−1.
From the representation of inner vertices, it is evident that no two vertices have the exact representation in the inner cycle.Case 2.
Whenj is even.
Let the partition resolving set beΠ=B1,B2,B3,B4, where B1=β1, B2=α7, B3=β2j+1, and B4=VPn,k\β1,α7,β2j+1; the following are the representations of the entire vertex set of Pn,k with respect to Π.
The representation of the outer vertices:(9)rα4ℓ+1|Π=1,5,j+22,0,ifℓ=0,ℓ+1,2,j−2ℓ+22,0,ifℓ=1,2,ℓ+1,ℓ+2,j−2ℓ+22,0,ifℓ=3,…,j2,ℓ−1,ℓ+2,2,0,ifℓ=j+22,j−ℓ+1,j−ℓ+5,2ℓ−j+22,0,ifℓ=j+42,…,j−1,rα4ℓ+2|Π=2,4,j+42,0,ifℓ=0,ℓ+2,2ℓ−1,j−2ℓ+42,0,ifℓ=1,2,ℓ+2,ℓ+2,j−2ℓ+42,0,ifℓ=3,…,j2,j−ℓ+2,j−ℓ+4,2ℓ−j+42,0,ifℓ=j+22,…,j−1,rα4ℓ+3|Π=3,3,j+42,0,ifℓ=0,ℓ+3,ℓ+1,j−2ℓ+42,0,ifℓ=2,3,…,j−22,ℓ+2,ℓ+1,3,0,ifℓ=j2,j−ℓ+2,j−ℓ+3,2ℓ−j+62,0ifℓ=j+22,…,j−1,rα4ℓ+4|Π=ℓ+3,3−2ℓ,j−2ℓ+22,0,ifℓ=0,1,ℓ+3,ℓ+2,j−2ℓ+22,0,ifℓ=2,…,j−22,ℓ+1,ℓ+2,3,0,ifℓ=j2,j−ℓ+1,j−ℓ+4,2ℓ−j+62,0,ifℓ=j+22,…,j−1.
The representation of outer vertices within themselves is unique, with no two vertices consisting of the exact representation.
Now, we exhibit the representations of the inner vertices:(10)rβ4ℓ+1|Π=1,3,j−22,p,ifℓ=1,ℓ,ℓ+1,j−2ℓ2,p,ifℓ=2,…,j−22,j−ℓ,ℓ+1,1,p,ifℓ=j+22,j−ℓ,j−ℓ+4,2ℓ−j2,p,ifℓ=j+42,…,j−1,rβ4ℓ+2|Π=3,3,j+62,p,ifℓ=0,ℓ+3,ℓ+1,j−2ℓ+62,p,ifℓ=1,2,…,j2,j−ℓ+3,j−ℓ+3,2ℓ−j+62,p,ifℓ=j+22,…,j−1,rβ4ℓ+3|Π=4,2,j+62,p,ifℓ=0,ℓ+4,ℓ,j−2ℓ+62,p,ifℓ=1,2,3,…,j−22,ℓ+3,ℓ,4,p,ifℓ=j2,j−ℓ+3,j−ℓ+2,2ℓ−j+82,p,ifℓ=j+22,…,j−1,rβ4ℓ+4|Π=4,3,j+42,p,ifℓ=0,ℓ+4,ℓ+1,j−2ℓ+42,p,ifℓ=1,2,3,…,j−22,ℓ+2,ℓ+1,4,p,ifℓ=j2,j−ℓ+2,j−ℓ+3,2ℓ−j+82,p,ifℓ=j+22,…,j−1.
The representations indicate that no two inner vertices among them have the exact representation.
The outer and inner vertices in the graph ofPn,k have distinct representations. Thus, Π=B1,B2,B3,B4, where B1=β1, B2=α3, B3=βn−2, and B4=VPn,k\β1,α3,βn−2 is the partition resolving set for odd j. Moreover, Π=B1,B2,B3,B4, where B1=β1, B2=α7, B3=β2j+1, and B4=VPn,k\β1,α7,β2j+1 is the partition resolving for even j. Hence,(11)pdPn,k≤4.From the following theoremp is 1, if the representation of the vertices belongs to the Π\B5 or B1,B2,B3,B4, otherwise p=0.Theorem 5.
LetPn,k is a generalized Petersen graph with n≥17, n≡1mod4. Then, pd Pn,k≤5.Proof.
Letn=4j+1, j≥4,∈ℤ+.Case 3.
Let the partition resolving set beΠ=B1,B2,B3,B4, where B1=β1, B2=α2, B3=β3, B4=α5, and B5=VPn,k\β1,α2,β3,α5; the following are the representations of the entire vertex set of Pn,k with respect to Π.
The representation of the outer vertices:(12)rα4ℓ+1|Π=1,1,3,3,0,ifℓ=0,ℓ+1,ℓ+3,ℓ+2,ℓ+1,0,ifℓ=2,…,g,j−ℓ+2,j−ℓ+4,j−ℓ+3,2ℓ−g,0,ifℓ=g+1,j−ℓ+2,j−ℓ+4,j−ℓ+3,j−ℓ+4,0,ifℓ=g+2,…,j−1,2,2,3,4,0,ifℓ=j,rα4ℓ+2|Π=3,3,3,1,0,ifℓ=1,ℓ+2,ℓ+2,ℓ+2,ℓ+2,0,ifℓ=2,3,…,g−1,j−ℓ+1,2ℓ−g+2,2ℓ−g+2,2ℓ−g+2,0,ifℓ=g,j−ℓ+1,j−ℓ+3,j−ℓ+3,j−ℓ+3,0,ifℓ=g+1,…,j−1,rα4ℓ+3|Π=3+ℓ,3ℓ+1,ℓ+1,2,0,ifℓ=0,1,ℓ+3,ℓ+3,ℓ+1,ℓ+3,0,ifℓ=2,…,g−1,j−ℓ+2,j−ℓ+2,2ℓ−g+1,2ℓ−g+3,0,ifℓ=g,j−ℓ+2,j−ℓ+2,j−ℓ+2,j−ℓ+4,0,ifℓ=g+1,…,j−1,rα4ℓ+4|Π=3+ℓ,3ℓ+2,ℓ+2,2ℓ+1,0,ifℓ=0,1,ℓ+3,ℓ+4,ℓ+2,ℓ+3,0,ifℓ=2,…,g−1,j−ℓ+2,j−ℓ+3,j−ℓ+1,2ℓ−g+3,0,ifℓ=g,j−ℓ+2,j−ℓ+3,j−ℓ+1,j−ℓ+4,0,ifℓ=g+1,…,j−2,3,3,2,5,p,ifℓ=j−1.
The representation of outer vertices between them is distinct concerningΠ.
The representation of the inner vertices:(13)rβ4ℓ+1|Π=ℓ,ℓ+2,ℓ+3,ℓ,p,ifℓ=1,2,3,…,g,2ℓ−g−1,j−ℓ+3,j−ℓ+4,2ℓ−g−1,p,ifℓ=g+1,j−ℓ+3,j−ℓ+3,j−ℓ+4,j−ℓ+3,p,ifℓ=g+2,…,j,rβ4ℓ+2|Π=3,1,3,3,p,ifℓ=0,ℓ+3,ℓ+1,ℓ+3,ℓ+1,p,ifℓ=2,3,…,g−1,j−ℓ,2ℓ−g+1,2ℓ−g+3,2ℓ−g+1,p,ifℓ=g,j−ℓ,j−ℓ+2,j−ℓ+4,j−ℓ+2,p,ifℓ=g+1,…,j−1,rβ4ℓ+3|Π=4+ℓ,ℓ+2,ℓ,ℓ+2,p,ifℓ=1,2,…,g−1,j−ℓ+3,j−ℓ+1,2ℓ−g,2ℓ−g+2,p,ifℓ=g,j−ℓ+3,j−ℓ+1,2ℓ−g−1,j−ℓ+3,p,ifℓ=g+1,j−ℓ+3,j−ℓ+1,j−ℓ+3,j−ℓ+3,p,ifℓ=g+2,…,j−1,rβ4ℓ+4|Π=4+ℓ,ℓ+3,ℓ+3,ℓ+2,p,ifℓ=0,1,…,g−2,2g−ℓ+2,2ℓ−g+4,j−ℓ,2ℓ−g+3,p,ifℓ=g−1,j−ℓ+3,j−ℓ+2,j−ℓ,2ℓ−g+2,p,ifℓ=g,j−ℓ+3,j−ℓ+2,j−ℓ,j−ℓ+3,p,ifℓ=g+1,…,j−1.
The inner vertices have unique representation with respect toΠ. Moreover, the outer and inner vertices have distinct representation among them. Thus, Π=B1,B2,B3,B4, where B1=β1, B2=α2, B3=β3, B4=α5, and B5=VPn,k\β1,α2,β3,α5, is the partition resolving set for n=4j+1. Hence,(14)pdPn,k≤5.Theorem 6.
LetPn,k be a generalized Petersen graph with n≥18, when n≡2mod4. Then, pd Pn,k≤5.Proof.
Letn=4j+2, j≥7∈ℤ+. The proof is split into two cases.Case 4.
Whenj is odd.
Let the partition resolving set beΠ=B1,B2,B3,B4, where B1=β1, B2=α3, B3=β2j+1, B4=α2j+3, and B5=VPn,k\β1,α3,β2j+1,α2j+3.
The representation of the outer vertices:(15)rα4ℓ+1|Π=ℓ+1,2,g+2,g−ℓ+3,0,ifℓ=0,1,ℓ+1,ℓ+3,g−ℓ+3,g−ℓ+3,0,ifℓ=2,3,…,g,j−ℓ+3,j−ℓ+3,ℓ−g+2,ℓ−g+1,0,ifℓ=g+1,…,j−1,3,3,g+2,g+2,0,ifℓ=j,rα4ℓ+2|Π=ℓ+2,2ℓ+1,g−ℓ+2,g−ℓ+4,0,ifℓ=0,1,ℓ+2,ℓ+3,g−ℓ+2,g−ℓ+4,0,ifℓ=2,3,…,g−1,g+2,ℓ+3,ℓ−g+2,j−2ℓ+2,0,ifℓ=g,g+1,…,j−1,j−ℓ+2,j−ℓ+4,ℓ−g+2,ℓ−g+2,0,ifℓ=g+2,…,j−1,2,3,g+3,g+3,0,ifℓ=j,rα4ℓ+3|Π=ℓ+3,ℓ+2,g−ℓ+1,g−ℓ+4,p,ifℓ=1,2,…,g−1,j−ℓ+1,ℓ+2,ℓ−g+1,2,p,ifℓ=g,g+1,j−ℓ+1,j−ℓ+4,ℓ−g+1,ℓ−g+3,p,ifℓ=g+2,…,j−1,rα4ℓ+4|Π=3,1,g+2,g+3,0,ifℓ=0,ℓ+3,ℓ+3,g−ℓ+2,g−ℓ+3,0,ifℓ=1,2,…,g−1,j−ℓ+2,g+3,ℓ−g+2,2ℓ−j+2,0,ifℓ=g,g+1,j−ℓ+2,j−ℓ+3,ℓ−g+2,ℓ−g+3,0,ifℓ=g+2,…,j−1.
The representation of the outer cycle vertices is distinct concerningΠ.
Now, the representation of the inner vertices:(16)rβ4ℓ+1|Π=1,3,g+2,g+1,p,ifℓ=1,ℓ,ℓ+2,g−ℓ+4,g−ℓ+2,p,ifℓ=2,3,…,g,ℓ,j−ℓ+2,ℓ−g+3,ℓ−g,p,ifℓ=g+1,g+2,j−ℓ+4,j−ℓ+2,ℓ−g+3,ℓ−g,p,ifℓ=g+3,g+4,…,j−2,j−ℓ+4,j−ℓ+2,j−κ+1,ℓ−g,p,ifℓ=j−1,j,rβ4ℓ+2|Π=ℓ+3,ℓ+2,g−ℓ+3,g−ℓ+3,p,ifℓ=0,1,…,g,j−ℓ+3,j−ℓ+3,ℓ−g+3,ℓ−g+1,p,ifℓ=g+1,…,j,rβ4ℓ+3|Π=4,1,g,g+2,p,ifϵ=0,ℓ+4,ℓ+1,g−ℓ,g−ℓ+3,p,ifℓ=1,2,…,g−2,ℓ+3,ℓ+1,1,4,p,ifℓ=g−1,j−ℓ,j−ℓ+2,1,3,p,ifℓ=g+1,j−ℓ,j−ℓ+3,ℓ−g,ℓ−g+2,p,ifℓ=g+2,…,j−1,rβ4ℓ+4|Π=ℓ+4,ℓ+2,g−ℓ+3,g−ℓ+2,p,ifℓ=0,1,…,g,j−ℓ+3,j−ℓ+2,ℓ−g+3,ℓ−g+2,p,ifℓ=g+1,g+2,…,j−1.
The representations of inner cycle vertices with respect toΠ are distinct. Both the outer and inner cycle vertices show distinct representations. Thus, Π=B1,B2,B3,B4, where B1=β1, B2=α3, B3=β2j+1, B4=α2j+3, and B5=VPn,k\β1,α3,β2j+1,α2j+3, is the partition resolving set when j is odd.Case 5.
Whenj is even.
Let the partition resolving set beΠ=B1,B2,B3,B4, where B1=β1, B2=α3, B3=β2j+1, B4=α2j+5, and B5=VPn,k\β1,α3,β2j+1,α2j+5.
The representation of the outer vertices:(17)rα4ℓ+1|Π=ℓ+1,2,j−2ℓ+22,j−2ℓ+62,0,ifℓ=0,1,ℓ+1,ℓ+3,j−2ℓ+22,j−2ℓ+62,0,ifℓ=2,3,…,j2,j−ℓ+3,j−ℓ+3,2ℓ−j+22,2ℓ−j+22,0,ifℓ=j+22,…,j,rα4ℓ+2|Π=ℓ+2,2ℓ+1,j−2ℓ+42,j+62,0,ifℓ=0,1,ℓ+2,ℓ+3,j−2ℓ+42,j−2ℓ+82,0,ifℓ=2,3,…,j−22,j−ℓ+2,j+62,2ℓ−j+42,j−2ℓ+3,0,ifℓ=j2,j+22,j−ℓ+2,j−ℓ+4,2ℓ−j+42,2ℓ−j+42,0,ifℓ=j+42,…,j−1,2,3,j+42,j+42,p,ifℓ=j,rα4ℓ+3|Π=ℓ+3,ℓ+2,j−2ℓ+42,j−2ℓ+82,p,ifℓ=0,1,…,j−22,j−ℓ+1,ℓ+2,2ℓ−j+62,2,0,ifℓ=j2,j+22,j−ℓ+1,j−ℓ+4,2ℓ−j+62,2ℓ−j+62,0,ifℓ=j+42,…,j−1,rα4ℓ+4|Π=3,1,j+22,j+62,p,ifℓ=0,ℓ+3,ℓ+3,j−2ℓ+22,j−2ℓ+62,0,ifℓ=1,…,j−22,j−ℓ+2,j−ℓ+3,2ℓ−j+62,2ℓ−j+1,0,ifℓ=j2,j+22,j−ℓ+2,j−ℓ+3,2ℓ−j+62,2ℓ−j+62,0,ifℓ=j+42,…,j−1.
The representations of the outer cycle vertices are distinct concerningΠ.
Now, the representations of the inner vertices:(18)rβ4ℓ+1|Π=ℓ,ℓ+2,j−2ℓ2,j−2ℓ+42,p,ifℓ=1,…,j−22,ℓ,ℓ,1,1,p,ifℓ=j+22,j−ℓ+4,j−ℓ+2,2ℓ−j2,2ℓ−j2,p,ifℓ=j+42,…,j,rβ4ℓ+2|Π=3,2,j+62,j+42,p,ifℓ=0,ℓ+3,ℓ+2,j−2ℓ+62,j−2ℓ+62,p,ifℓ=1,…,j2,j−ℓ+3,j−ℓ+3,2ℓ−j+62,2ℓ−j+22,p,ifℓ=j+22,…,j.(19)rβ4ℓ+3|Π=4,1,j+22,j+22,p,ifℓ=0,ℓ+4,ℓ+1,j−2ℓ+62,j−2ℓ+62,p.ifℓ=1,2,…,j−42,j−ℓ,ℓ+1,4,j−2ℓ+62,p,ifℓ=j−22,j2,j−ℓ,j−ℓ+3,2ℓ−j+82,2ℓ−j+42,pifℓ=j+22,…,j−2,1,4,2ℓ−j+42,2ℓ−j+42,p,ifℓ=j−1.(20)rβ4ℓ+4|Π=ℓ+4,ℓ+2,j−2ℓ+42,2ℓ−j+42,p,ifℓ=0,1,…,j−22,j−ℓ+3,j−ℓ+2,2ℓ−j+82,2ℓ−j+42,p,ifℓ=j2,j+22,…,j−1.
The representations of the inner cycle vertices are distinct. Also, outer and inner vertices are distinct as well with respect toΠ. Thus, Π=B1,B2,B3,B4, where B1=β1, B2=α3, B3=β2j+1, B4=α2j+5, and B5=VPn,k\β1,α3,β2j+1,α2j+5, is the partition resolving set, when j is even. From above facts, we have(21)pdPn,k≤5.Theorem 7.
LetPn,k be a generalized Petersen graph with n≥19 and n≡3mod4. Then, pd Pn,k≤5.Proof.
Whenn≡3mod4, n=4j+3, and j≥7∈ℤ+. The proof is divided in two cases.Case 6.
Whenj is odd.
Let the partition resolving set beΠ=B1,B2,B3,B4, where B1=β1, B2=α3, B3=β2j+1, B4=α2j+2, and B5=VPn,k\β1,α3,β2j+1,α2j+2. The representation of vertices with respect to Π is presented.
The representations of the outer vertices:(22)rα4ℓ+1|Π=ℓ+1,2,g−ℓ+3,g+3,0,ifℓ=0,1,ℓ+1,ℓ+3,g−ℓ+3,g−ℓ+4,0,ifℓ=2,…,g−1,ℓ+1,ℓ+3,3,j−2ℓ+2,0,ifℓ=g,g+1,j−ℓ+3,j−ℓ+4,ℓ−g+2,ℓ−g+2,0,ifℓ=g+2,…,j.(23)rα4ℓ+2|Π=ℓ+2,2ℓ+1,g−ℓ+2,g−ℓ+4,p,ifℓ=0,1,ℓ+2,ℓ+3,g−ℓ+2,g−ℓ+4,p,ifℓ=2,…,g−1,ℓ+2,g+3,ℓ−g+2,2,p,ifℓ=g,g+1,j−ℓ+3,j−ℓ+3,ℓ−g+2,ℓ−g+3,p,ifℓ=g+2,…,j−1,3,3,g+2,g+4,p,ifℓ=j.(24)rα4ℓ+3|Π=ℓ+3,ℓ+2,g−ℓ+1,g−ℓ+3,0,ifℓ=1,2,…,g−1,j−ℓ+2,ℓ+2,ℓ−g+1,2ℓ−j+2,0,ifℓ=g,g+1,j−i+2,j−ℓ+4,ℓ−g+1,ℓ−g+3,0,ifℓ=g+2,…,j−1,2,3,g+2,g+3,0,ifℓ=j.(25)rα4ℓ+4|Π=3,1,g+2,g+2,0,ifℓ=0,ℓ+3,ℓ+3,g−ℓ+2,g−ℓ+2,0,ifℓ=1,2,…,g−1,j−ℓ+1,j−ℓ+4,ℓ−g+2,ℓ−g+2,0,ifℓ=g+1,…,j−1.
The representation of the outer cycle vertices with respect toΠ is distinct.
Now, the representation of the inner vertices:(26)rβ4ℓ+1|Π=ℓ,ℓ+2,g−ℓ+4,g−ℓ+3,p,ifℓ=1,2,…,g,ℓ,j−ℓ+3,ℓ−g+3,ℓ−g+1,p,ifℓ=g+1,g+2,j−ℓ+4,j−ℓ+3,ℓ−g+3,ℓ−g+1,p,ifℓ=g+3,g+4,…,j.(27)rβ4ℓ+2|Π=ℓ+3,ℓ+2,g−ℓ+3,g−ℓ+3,p,ifℓ=0,1,…,g,j−ℓ+4,j−ℓ+2,ℓ−g+3,ℓ−g+2,p,ifℓ=g+1,g+2,…,j−2,j−ℓ+4,j−ℓ+2,j−κ+1,ℓ−g+2,p,ifℓ=j−1,j.(28)rβ4ℓ+3|Π=ℓ+4,ℓ+1,g−ℓ,g−ℓ+2,p,ifℓ=0,1,…,g−1,ℓ+2,ℓ+1,1,3,p,ifℓ=g+1,j−ℓ+3,j−ℓ+3,ℓ−g,ℓ−g+2,p,ifℓ=g+2,…,j−1,3,3,ℓ−g,ℓ−g+1,p,ifℓ=j.(29)rβ4ℓ+4|Π=4,2,g+2,g+1,p,ifℓ=0,ℓ+4,ℓ+2,g−ℓ+3,g−ℓ+1,p,ifℓ=1,2,…,g−2,j−ℓ,ℓ+2,g−ℓ+3,g−ℓ+1,p,ifℓ=g−1,g,j−ℓ,j−ℓ+3,ℓ−g+3,g−ℓ+1,p,ifℓ=g+1,…,j−1.
The representations of the inner cycle vertices are distinct with respect toΠ. Also, the outer and inner vertices have distinct representations as well. Thus, Π=B1,B2,B3,B4, where B1=β1, B2=α3, B3=β2j+1, B4=α2j+2, and B5=VPn,k\β1,α3,β2j+1,α2j+2, is the partition resolving set when j is odd.Case 7.
Whenj is even.
Let the partition resolving set beΠ=B1,B2,B3,B4, where B1=β1, B2=α3, B3=β2j+1, B4=α2j+3, and B5=VPn,k\β1,α3,β2j+1,α2j+3.
The representation of the outer vertices:(30)rα4ℓ+1|Π=ℓ+1,2,j−2ℓ+22,j+62,0,ifℓ=0,1,ℓ+1,ℓ+3,j−2ℓ+22,j−2ℓ+82,0,ifℓ=2,…,j−22,ℓ+1,j+62,2ℓ−j+22,2,0,ifℓ=j2,j+22,j−ℓ+3,j−ℓ+4,2ℓ−j+22,2ℓ−j+62,0,ifℓ=j+22,…,j.(31)rα4ℓ+2|Π=ℓ+2,2ℓ+1,j−2ℓ+42,j−2ℓ+62,0,ifℓ=0,1,ℓ+2,ℓ+3,j−2ℓ+42,j−2ℓ+62,0,ifℓ=2,…,j−22,j+42,j−ℓ+3,2ℓ−j+42,2ℓ−j+1,0,ifℓ=j2,j+22,j−ℓ+3,j−ℓ+3,2ℓ−j+42,2ℓ−j+62,0,ifℓ=j+42,…,j.(32)rα4ℓ+3|Π=ℓ+3,ℓ+2,j−2ℓ+42,j−2ℓ+42,p,ifℓ=1,…,j−22,j−ℓ+2,j−ℓ+4,2ℓ−j+62,2ℓ−j+42,p,ifℓ=j+22,…,j,2,3,j+42,j+42,p,ifℓ=j.(33)rα4ℓ+4|Π=ℓ+3,ℓ+1,j+22,j+62,0,ifℓ=0,ℓ+3,ℓ+3,j−2ℓ+22,j−2ℓ+62,0,ifℓ=1,…,j−42,j−ℓ+1,ℓ+3,2ℓ−j+62,j−2ℓ+1,0,ifℓ=j−22,j2,j−ℓ+1,j−ℓ+4,2ℓ−j+62,2ℓ−j+62,0,ifℓ=j+22,…,j−1.
The representation of the outer cycle vertices with respect toΠ is distinct.
Now, the representation of the inner vertices:(34)rβ4ℓ+1|Π=ℓ,ℓ+2,j−2ℓ2,j−2ℓ+62,p,ifℓ=1,…,j−22,ℓ,ℓ+1,1,3,p,ifℓ=j+22,j−ℓ+4,j−ℓ+3,2ℓ−j2,2ℓ−j+42,pifℓ=j+42,…,j.(35)rβ4ℓ+2|Π=ℓ+3,ℓ+2,j+2ℓ+22,j−2ℓ+42,p,ifℓ=0,1,ℓ+3,ℓ+2,j−2ℓ+62,j−2ℓ+42,p,ifℓ=2,3,…,j2,j−ℓ+4,j−ℓ+2,2ℓ−j+62,2ℓ−j+42,pifℓ=j+22,…,j.(36)rβ4ℓ+3|Π=ℓ+4,ℓ+1,j−2ℓ+62,j−2ℓ+22,p,ifℓ=0,1,…,j−22,ℓ+3,ℓ+1,4,1,p,ifℓ=j2,j−ℓ+3,j−ℓ+3,2ℓ−j+82,2ℓ−j+22,p,ifℓ=j+22,…,j−1,3,3,j+62,j+22,p,ifℓ=j.(37)rβ4ℓ+4|Π=ℓ+4,ℓ+2,j−2ℓ+42,j−2ℓ+42,p,ifℓ=0,1,…,j−42,j−ℓ,ℓ+2,2ℓ−j+82,j−2ℓ+42,p,ifℓ=j−22,j2,j−ℓ,j−ℓ+3,2ℓ−j+82,2ℓ−j+42,p,ifℓ=j+22,…,j−2,1,4,j+22,j+22,p,ifℓ=j−1.
The representation of the inner cycle vertices is distinct. Moreover, the outer and inner vertices are distinct as well. Thus,Π=B1,B2,B3,B4, where B1=β1, B2=α3, B3=β2j+1, B4=α2j+3, and B5=VPn,k\β1,α3,β2j+1,α2j+3, is the partition resolving set when j is even. From all these facts, we conclude that(38)pdPn,k≤5.Example 1.
LetP17,k be a generalized Petersen graph; then, pdPn,k≤5.Proof.
Let the partition resolving set beΠ=B1,B2,B3,B4, where B1=β1, B2=α2, B3=β3, B4=α5, and B5=VP17,k\β1,α2,β3,α5. The representation of the entire vertex set of P17,k with respect to Π is presented in Table 1.Table 1
Representation of the generalized Petersen graphP17,k.
VerticesRepresentationrα1|Π1,1,3,3,0rα2|Π2,0,2,3,0rα3|Π3,1,1,2,0rα4|Π3,2,2,1,0rα5|Π2,3,3,0,0rα6|Π3,3,3,1,0rα7|Π4,4,2,2,0rα8|Π4,5,3,3,0rα9|Π3,5,4,3,0rα10|Π3,4,4,4,0rα11|Π4,4,3,5,0rα12|Π4,5,3,5,0rα13|Π3,5,4,4,0rα14|Π2,4,4,4,0rα15|Π3,3,3,5,1rα16|Π3,3,2,5,0rα17|Π2,2,3,4,1rβ1|Π0,2,4,2,1rβ2|Π3,1,3,3,1rβ3|Π4,2,0,3,1rβ4|Π4,3,3,2,1rβ5|Π1,3,4,1,1rβ6|Π3,2,4,2,1rβ7|Π5,3,1,3,1rβ8|Π5,4,3,3,1rβ9|Π2,4,5,2,1rβ10|Π2,3,5,3,1rβ11|Π5,3,2,4,1rβ12|Π5,4,2,4,1rβ13|Π3,4,5,3,1rβ14|Π1,3,5,3,1rβ15|Π4,2,3,4,1rβ16|Π4,3,1,4,1rβ17|Π3,3,4,3,1


## 4. Conclusion

In this paper, authors provide the sharp bounds of the partition dimension for the generalized Petersen networkPn,k, and by using Theorem 1.3 for lower bound, we concluded that(39)3≤pdPn,k≤4,ifn≥20andn≡0mod4,5,ifn≥17andn≡1,2,3mod4.Theorem4 discusses the partitioning of generalized Petersen network when n≡0mod4, and Theorems 5–7 contain the partitioning when n≡1,2,3mod4, respectively.



---

*Source: 5592476-2021-10-29.xml*