MATHEMATICA BOHEMICA, Vol. 125, No. 2, pp. 155-168 (2000)

The directed distance dimension of oriented graphs

Gary Chartrand, Michael Raines, Ping Zhang

Gary Chartrand, Michael Raines, Ping Zhang, Department of Mathematics and Statistics Western Michigan University Kalamazoo, MI 49008, USA, e-mail:

Abstract: 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.

Keywords: oriented graphs, directed distance, resolving sets, dimension

Classification (MSC2000): 05C12, 05C20

Full text of the article:

[Previous Article] [Next Article] [Contents of this Number]
© 2005 ELibM and FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition