THE PARTITION DIMENSION GRAF OF SUBDIVISION OPERATION

• Main Author: (NIM: 30111009), AMRULLAH
• Format: Dissertations
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/19866
• Institution: Institut Teknologi Bandung

The concept of partition dimension graph was first introduced by Chartrand, et al, (1998). This concept is an extention of the metric dimension concept proposed by Slater (1975) and Harary & Melter (1976). This concept has several applications, for instance representation of chemical compounds, problems of pattern recognition, image processing, data structures, and robot navigation (Yero dkk., 2011). Let G(V,E) beaconnectedgraphand Π = {L1,L2,...,Lk}beapartitionof V (G). There presentation of vertexv respecttoΠisthek−vectorwhosei-thcomponentis the distance between v andLi. If distinct vertices of Ghave distinct representations, then Π is called a resolving partition of G. The partition dimension of G is the smallest positive integer k such that G has a resolving partition with k partition classes. Research of partition dimension of graph has been widely carried out. One of the results is characterization of graphs based on their partition dimension. Paths are the only graphs with partition dimension 2. While complete graphs are the only graphs whose partition dimension equal to their order. Meanwhile graphs of order n with partition dimension n−1 are K1,n−1, Kn −e, or K1 + (K1 ∪Kn−2), and there are 23 non isomorphic graphs whose partition dimensions are n−2. Partition dimensionof the product graph shave been studied by several researchers, for instance corona product, strong product, and Cartesian product. In this dissertation, we determine partition dimension of subdivision graph. The subdivision graph S(G(e;k)) is a graph obtained from G by replacing one edge with a path of length k + 1. As results, we obtain partition dimension of S(G(e;k)) where G is a firecracker and caterpillar. In general, we give an upper bound on partition dimension of S(G(e;k)) for any connected graph G. We also study subdivision graph S(G) obtained from G by replacing each edge with a path of length 2. Furthermore, we obtain partition dimension S(G) where G is a star and complete graph.