ON THE PARTITION DIMENSION OF DISCONNECTED GRAPHS

• Main Author: Oktia Haryeni, Debi
• Format: Theses
• Language: Indonesia
• Subjects: Matematika
• Online Access: https://digilib.itb.ac.id/gdl/view/33603
• Institution: Institut Teknologi Bandung

The concept of partition dimension of a connected graph was introduced by Chartrand et al. [12] in 1998. This is an expansion of metric dimension concept introduced by Slater [24] in 1975 and Harary & Melter [9] in 1976. The partition dimension in a graph G is dened as the minimum cardinality of an ordered partition of a vertex set V (G) such that every vertex, with respect to the partition, has distinct representation. In this case, the representation of a vertex is expressed in terms of the distances of this vertex to all partition classes. Determining the partition dimension of a graph is an NP-hard problem [14]. It means that there is no efficient algorithm to and a partition dimension for an arbitrary graph. Therefore, one determine partition dimension for a certain class of graph or characterize some graphs satisfying a given partition dimension. Some results have been found, such a characterizing of graphs of order n whose partition dimension are 2; n; n-1 in [13], and n-2 in [19]. Partition dimension for some classes of graph also have been determined. Ones determined the partition dimension of a corona product of two graphs in [4, 5, 8, 7], and a cartesian product graphs in [15] as well. However, the study of partition dimension of a graph is limited for connected graphs only. Therefore, we will extend the concept of partition dimension such that it can be applied for all graph, including for disconnected ones. We give the upper .......