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