PARTITION DIMENSION OF ORIENTED GRAPH

• Main Author: SHOFIYATI (NIM: 20113038), NUR
• Format: Theses
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/20375
• Institution: Institut Teknologi Bandung

The concept of metric dimension was introduced by Harary and Melter [6] at 1976 and metric dimension for orientation graph was first studied by Chartrand et al. [2] at 1998. Let D be an oriented graph and u,v ∈ V (D). Distance from u to v, denoted by d(u,v), is the number of arcs in the shortest u − v path or ∞ if a u − v path does not exist. For S ⊂ V (D), the distance from v to S, d(v,S), is defined as min{d(v,x)|x ∈ S}. A vertex x of D is said to resolve two distinct vertices u,v in D if d(u,x) 6= d(v,x). S is said to be a resolving set if d(u,S) 6= d(v,S) for every pair of distinct vertices u and v. A partition Π = {P1,P2,...,Pk}of V (D) is a resolving partition of D if each vertices in V (D) there exists i so that Pi is a resolving set of those vertices. The minimum cardinality of a resolving partition of D is called the partition dimension of D and is denoted by pd(D). In this tesis, we study characterization of strongly connected oriented graphs with partition dimension two and construct oriented graphs with partition dimension three.