On metric dimension of digraphs

Min Feng, Kaishun Wang, Yuefeng Yang

Published 2020-11-24Version 1

Using the two way distance, we first introduce resolving sets and metric dimension of a strongly connected digraph $\Gamma$. Then we establish lower and upper bounds for the number of arcs in $\Gamma$ by using the diameter and metric dimension of $\Gamma$, and characterize all digraphs attaining the lower or upper bound. We also study a digraph with metric dimension $1$ and classify all vertex-transitive digraphs having metric dimension $1$. Finally, we characterize all digraphs of order $n$ with metric dimension $n-2$.