Strong Oriented Graphs with Largest Directed Metric Dimension

Rinovia Simanjuntak
Institut Teknologi Bandung

Yozef G. Tjandra
Institut Teknologi Bandung



Content: Let $D$ be a strongly connected oriented graph with vertex-set $V$ and arc-set $E$. The distance from a vertex $u$ to another vertex $v$, $d(u,v)$ is the minimum length of oriented paths from $u$ to $v$. Suppose $B=\{b_1,b_2,b_3,...b_k\}$ is a nonempty ordered subset of $V$. The representation of a vertex $v$ with respect to $B$, $r(v|B)$, is defined as a vector $(d(v,b_1), d(v,b_2), \ldots, d(v,b_k))$. If any two distinct vertices $u,v$ satisfy $r(u|B) \neq r(v|B)$, then $B$ is a resolving set of $D$. If the cardinality of $B$ is minimum then $B$ is a basis of $D$ and the cardinality of $B$ is the directed metric dimension of $D$, $dim(D)$. We proved that if $D$ is a strongly connected oriented graph of order $n \geq 4$, then $dim(D) \leq n-3$. Furthermore, we characterized strong oriented graphs attaining the upper bound, i.e., strong oriented graphs of order $n$ and metric dimension $n-3$.

Back to all abstracts