On the dimension of oriented graphs
Abstract
For a vertex v of an oriented graph D and an ordered set W = {w1, w2, ⋯, wk} of vertices of D, the (directed distance) representation of v with respect to W is the ordered k-tuple r(v\W) = (d(v, w1), d(v, w2), ⋯, d(v, wk)), where d(v, wi) is the directed distance from v to wi. 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 dim(D)/n. It is shown that for every rational number r ∈ (0, 1), there exists an oriented graph D with dr(D) = r. Furthermore, for every rational number r ∈ (0, 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 S of graphs G with ORD(G) = k for each G ∈ S. Also, it is shown that limn→∞ ORD(Kn) = ∞.
