ON THE PARTITION DIMENSION OF DISCONNECTED GRAPHS
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...
Saved in:
| Main Author: | |
|---|---|
| Format: | Theses |
| Language: | Indonesia |
| Subjects: | |
| Online Access: | https://digilib.itb.ac.id/gdl/view/33603 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Institut Teknologi Bandung |
| Language: | Indonesia |
| Summary: | 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
....... |
|---|