On the Dimension of Oriented Graphs



For a vertex $v$ of an oriented graph $D$ and an ordered set $W$ $=$ \{$w_1$, $w_2$, $\cdots$, $w_k$\} of vertices of $D$, the (directed distance) representation of $v$ with respect to $W$ is the ordered $k$-tuple $r(v|W) = ( d(v, w_1), d(v, w_2), \cdots, d(v, w_k) )$, where $d(v, w_i)$ is the directed distance from $v$ to $w_i$. The set $W$ is a resolving set for $D$ if every two distinct vertices of $D$ have distinct representations. The minimum cardinality of a resolving set for $D$ is the (directed distance) dimension $\dim (D)$. The dimension ratio $dr (D)$ of an oriented graph $D$ of order $n$ is $\frac{\dim (D)}{n}$. It is shown that for every rational number $r \in (0, 1)$, there exists an oriented graph $D$ with $dr (D) = r$. Furthermore, for every rational number $r \in (0, \frac{1}{2})$, there exists a tournament $T$ with $dr (T) = r$. The upper orientable dimension $ORD (G)$ of an oriented graph $G$ is the maximum value of $\dim (D)$ among the orientations $D$ of $G$ for which $\dim (D)$ is defined. It is shown for every positive integer $k$, there exists an infinite class $\cS$ of graphs $G$ with $ORD (G) = k$ for each $G \in \cS$. Also, it is shown that $\lim_{n \rightarrow \infty} ORD (K_n) = \infty$.