ON THE PARTITION DIMENSION OF CAVEMAN GRAPH,
GENERALIZED PETERSEN GRAPH, AND
K
m
∗
2
K
n
GRAPH
Meta Ila ani, Tri Atmojo Kusmayadi
Department of Mathematics
Faculty of Mathematics and Natural Sciences
Sebelas Maret University
Abstract.
Let
G
be a connected graph with vertex set
V
(
G
) =
{
v
1
;v
2
;:::;v
n
}
and
edge set
E
(
G
) =
{
e
1
;e
2
;:::;e
n
}
. Those vertices are divided into
k
-partition, denoted by
S
1
;S
2
;:::;S
k
. Let =
{
S
1
;S
2
;:::;S
k
}
be an ordered
k
-partition. The representation
for every vertex
V
(
G
) of is a minimum distance of a vertex to other vertices, denoted
by
r
(
v
|
) = (
d
(
v;S
1
)
;d
(
v;S
2
)
;:::;d
(
v;S
k
)). If every vertex has distinct representation,
is called a resolving
k
-partition. Minimum cardinality of
k
-partition of
V
(
G
) is called
by partition dimension of
G
, denoted by
pd
(
G
). In this research, we determine partition
dimension of caveman graph
C
(
n;k
), generalized Petersen graph
P
(
n;k
), and
K
m
∗
2
K
n
graph.
Keywords
: Partition dimension, caveman graph, generalized Petersen graph,
K
m
∗
2
K
n
graph.
1.
Introduction
There are many concepts in graph discussed by researchers. One of those
concepts is partition dimension. This concept is introduced by Chartrand et al. [4]
in 1998. Partition dimension of
G
or
pd
(
G
) is minimum cardinality of a resolving
k
-partition of
V
(
G
).
The concept of partition dimension has been applied frequently in some graph
classes. In 1998, Chartrand et al. [4] studied about partition dimension of path
graph, complete graph, and cycle graph. Then, Asmiati [2] found partition dimension
of amalgamation of stars graph in 2012. Thereafter, in 2016, Apriliani [1] determined
partition dimension of antiprism graph, mongolian tent graph, and stacked book
graph. Also in 2016, Dewi [5] determined partition dimension of some graph classes,
such as lollipop graph, generalized Jahangir graph, and
C
n
∗
2
K
m
graph. In this
research, we determine partition dimension of caveman graph
C
(
n; k
) for
n; k
≥
3,
generalized Petersen graph
P
(
n; k
) for
n
≥
5
; k
= 2 and
n
≥
8
; k
= 3, and
K
m
∗
2
K
n
graph for
m; n
≥
3.
