ON THE PARTITION DIMENSION OF DISCONNECTED GRAPHS WITH CERTAIN COMPONENTS

• Main Author: Oktia Haryeni (NIM: 30115002), Debi
• Format: Dissertations
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/26438
• Institution: Institut Teknologi Bandung

Let G=(V,E) be an arbitrary (connected or disconnected) graph and &#928; be a partition of V(G). The representation of a vertex v&#8712;V(G) with respect to the partition &#928; is a distance vector of the vertex v with respect to &#928;. Furthermore, &#928; is called a resolving partition of G if every vertex of G has distinct representation with respect to &#928;. The partition dimension of G is the minimum cardinality of a resolving partition in G. <br /> <br /> Determining the partition dimension of any graph is an NP-complete problem. This means that there is no polynomial time solution known to find the partition dimension of an arbitrary graph. Therefore, the study of the partition dimension is restricted for certain classes of graph or by characterizing graphs with a certain partition dimension. For a connected graph G, the partition dimension of some classes of G have been obtained, such as for paths, cycles, stars, double stars, complete graphs, caterpillar graphs, wheels, bipartite graphs and complete r-partite graphs. For any tree T not isomorphic to the paths, the result was only for the upper bound of the partition dimension of T. The characterizations of connected graphs of order n&#8805;2 have been studied for the graphs with partition dimension 2, n-2,n-1 or n. The remaining characterization is still an open problem until now. The study of the partition dimension also has been obtained from some graph operations, such as Cartesian product, strong product, corona product and subdivision. <br /> <br /> For a disconnected graph G, the necessary and sufficient conditions of a finite partition dimension of G have been derived. However, determining the partition dimension of disconnected graph is still limited until now. There were only a few results studying the partition dimension of disconnected graph containing a complete graph as a component or a disconnected graph with some homogeneous components, namely paths, stars, double stars or some cycles. <br /> <br /> In this dissertation, the study of the partition dimension of graphs, especially a disconnected graph, is continued. The partition dimension of two-component graphs is discussed, in particular where one of the component is a path or a cycle, or the two components have the same partition dimension. Furthermore, the partition dimension for disconnected graphs with homogeneous components are also considered, namely the graphs containing cycles or complete bipartite graphs as components. The sufficient conditions of graph containing cycles with different length and having the partition dimension 3 are given. By those conditions, some families of graphs, either connected or disconnected, are constructed in such a way that these new graphs have partition dimension 3 as well. For disconnected graphs containing homogeneous complete bipartite graphs, the necessary conditions for the graphs with finite partition dimension are given. Moreover, the characterization of complete bipartite graphs with certain partition dimensions is also studied. In this dissertation, the upper bound of partition dimension of hair graph of G, namely a graph obtained by identifying an end point of new paths to some vertices of G, is also established. In addition, many classes of hair graphs G having the same partition dimension with G are also presented, some with the partition dimension 3. The upper bound of partition dimension of a forest with homeomorphic trees is derived as well. <br />