THE CONNECTED GRAPH OF ORDER n ? 9 WITH DIAMETER 2 AND PARTITION DIMENSION n-3

• Main Author: Salmun, Ahmad
• Format: Theses
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/34185
• Institution: Institut Teknologi Bandung

Let G be a connected graph and u,v ? V(G),u ? v. The distance between two vertices u,v?V(G), denoted by d(u,v), is the length of a shortest path between them. The diameter of G, denoted by diam(G)=max?{d(u,v)|u,v? V(G)}. Let S?V(G) and S={s_1,…,s_k }. For every v?V(G) define the representation r(v|S) by the k-tuple (d(v,s_1 ), …, d(v,s_k)). If for every two distinct vertices u and v we have r(u|S) ? r(v|S), then S is called a resolving set of G. Now, let S?V(G) and v ? V(G), and ?=(S_1, …, S_k) is an ordered k-partition of V(G). The representation of v with respect to ? is the k-tuple r(v??)=(d(v,S_1 ), …, d(v,S_k)). If all the representation are distinct, then the partition ? is called by a resolving partition. The partition dimension of G, denoted by pd(G), is a smallest integer k such that G has a resolving partition with k-partition classes. Determining the partition dimension of connected graphs is a Non-deterministic Polynomial Complete (NP-Complete) Problem. Therefore, the study of the partition dimension of connected graphs is restricted for certain classes of graph. The partition dimension of connected graphs has been determined such as path P_n, complete K_n, characterization of connected graphs with pd(G)=n-1, and characterization of connected graphs with pd(G)=n-2. This project discusses about connected graph of order n ? 9 with diameter 2 and pd(G)=n-3. This study shows that graph G1, G2, H1, H2,...H4, K1 + (K1 ? K1,n-3), dan (K2+K1,n-3)have partition dimension n-3 with n is the order of such graphs.