Geodesic
The directed distance dimension of oriented graphs
Mathematica Bohemica, Tome 125 (2000) no. 2, pp. 155-168

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
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.
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.
DOI : 10.21136/MB.2000.125961
Classification : 05C12, 05C20
Keywords: oriented graphs; directed distance; resolving sets; dimension 
Chartrand, Gary; Raines, Michael; Zhang, Ping. The directed distance dimension of oriented graphs. Mathematica Bohemica, Tome 125 (2000) no. 2, pp. 155-168. doi: 10.21136/MB.2000.125961
@article{10_21136_MB_2000_125961,
     author = {Chartrand, Gary and Raines, Michael and Zhang, Ping},
     title = {The directed distance dimension of oriented graphs},
     journal = {Mathematica Bohemica},
     pages = {155--168},
     year = {2000},
     volume = {125},
     number = {2},
     doi = {10.21136/MB.2000.125961},
     mrnumber = {1768804},
     zbl = {0963.05045},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2000.125961/}
}
TY  - JOUR
AU  - Chartrand, Gary
AU  - Raines, Michael
AU  - Zhang, Ping
TI  - The directed distance dimension of oriented graphs
JO  - Mathematica Bohemica
PY  - 2000
SP  - 155
EP  - 168
VL  - 125
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2000.125961/
DO  - 10.21136/MB.2000.125961
LA  - en
ID  - 10_21136_MB_2000_125961
ER  - 
%0 Journal Article
%A Chartrand, Gary
%A Raines, Michael
%A Zhang, Ping
%T The directed distance dimension of oriented graphs
%J Mathematica Bohemica
%D 2000
%P 155-168
%V 125
%N 2
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2000.125961/
%R 10.21136/MB.2000.125961
%G en
%F 10_21136_MB_2000_125961

[1] G. Chartrand L. Eroh M. Johnson O. R. Oellermann: Resolvability in graphs and the metric dimension of a graph. Preprint. | MR

[2] F. Harary R. A. Melter: On the metric dimension of a graph. Ars Combin. 2 (1976), 191-195. | MR

[3] P. J. Slater: Leaves of trees. Congress. Numer. 11, (1975), 549-559. | MR | Zbl

[4] P. J. Slater: Dominating and reference sets in graphs. J. Math. Phys. Sci. 22 (1988), 445-455. | MR

Cité par Sources :