×

The directed distance dimension of oriented graphs. (English) Zbl 0963.05045

Summary: For a vertex \(v\) of a connected oriented graph \(D\) and an ordered set \(W=\{w_1,w_2,\dots ,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),\dots ,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.

MSC:

05C12 Distance in graphs
05C20 Directed graphs (digraphs), tournaments