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: zhang@math-stat.wmich.edu

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