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$.