| Title:
|
The directed distance dimension of oriented graphs (English) |
| Author:
|
Chartrand, Gary |
| Author:
|
Raines, Michael |
| Author:
|
Zhang, Ping |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
125 |
| Issue:
|
2 |
| Year:
|
2000 |
| Pages:
|
155-168 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
oriented graphs |
| Keyword:
|
directed distance |
| Keyword:
|
resolving sets |
| Keyword:
|
dimension |
| MSC:
|
05C12 |
| MSC:
|
05C20 |
| idZBL:
|
Zbl 0963.05045 |
| idMR:
|
MR1768804 |
| DOI:
|
10.21136/MB.2000.125961 |
| . |
| Date available:
|
2009-09-24T21:41:50Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/125961 |
| . |
| Reference:
|
[1] G. Chartrand L. Eroh M. Johnson O. R. Oellermann: Resolvability in graphs and the metric dimension of a graph.Preprint. MR 1780464 |
| Reference:
|
[2] F. Harary R. A. Melter: On the metric dimension of a graph.Ars Combin. 2 (1976), 191-195. MR 0457289 |
| Reference:
|
[3] P. J. Slater: Leaves of trees.Congress. Numer. 11, (1975), 549-559. Zbl 0316.05102, MR 0422062 |
| Reference:
|
[4] P. J. Slater: Dominating and reference sets in graphs.J. Math. Phys. Sci. 22 (1988), 445-455. MR 0966610 |
| . |
