# Article

**Keywords:**

oriented graphs; directed distance; resolving sets; dimension

**Summary:**

For a vertex $v$ of a connected 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\bigm|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)$ of $D$. The dimension of a connected oriented graph need not be defined. Those oriented graphs with dimension 1 are characterized. We discuss the problem of determining the largest dimension of an oriented graph with a fixed order. It is shown that if the outdegree of every vertex of a connected oriented graph $D$ of order $n$ is at least 2 and $\dim(D)$ is defined, then $\dim(D) \leq n-3$ and this bound is sharp.

References:

[1] G. Chartrand L. Eroh M. Johnson O. R. Oellermann:

**Resolvability in graphs and the metric dimension of a graph**. Preprint.

MR 1780464
[2] F. Harary R. A. Melter:

**On the metric dimension of a graph**. Ars Combin. 2 (1976), 191-195.

MR 0457289
[4] P. J. Slater:

**Dominating and reference sets in graphs**. J. Math. Phys. Sci. 22 (1988), 445-455.

MR 0966610