The directed distance dimension of oriented graphs

Gary Chartrand; Michael Raines; Ping Zhang

Mathematica Bohemica (2000)

  • Volume: 125, Issue: 2, page 155-168
  • ISSN: 0862-7959

Abstract

top
For a vertex v of a connected oriented graph D and an ordered set W = { w 1 , w 2 , , 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 ) , , 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 ) n - 3 and this bound is sharp.

How to cite

top

Chartrand, Gary, Raines, Michael, and Zhang, Ping. "The directed distance dimension of oriented graphs." Mathematica Bohemica 125.2 (2000): 155-168. <http://eudml.org/doc/248478>.

@article{Chartrand2000,
abstract = {For a vertex $v$ of a connected oriented graph $D$ and an ordered set $W = \lbrace w_1,w_2,\cdots ,w_k\rbrace $ 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) \le n-3$ and this bound is sharp.},
author = {Chartrand, Gary, Raines, Michael, Zhang, Ping},
journal = {Mathematica Bohemica},
keywords = {oriented graphs; directed distance; resolving sets; dimension; oriented graphs; directed distance; resolving sets; dimension},
language = {eng},
number = {2},
pages = {155-168},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {The directed distance dimension of oriented graphs},
url = {http://eudml.org/doc/248478},
volume = {125},
year = {2000},
}

TY - JOUR
AU - Chartrand, Gary
AU - Raines, Michael
AU - Zhang, Ping
TI - The directed distance dimension of oriented graphs
JO - Mathematica Bohemica
PY - 2000
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 125
IS - 2
SP - 155
EP - 168
AB - For a vertex $v$ of a connected oriented graph $D$ and an ordered set $W = \lbrace w_1,w_2,\cdots ,w_k\rbrace $ 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) \le n-3$ and this bound is sharp.
LA - eng
KW - oriented graphs; directed distance; resolving sets; dimension; oriented graphs; directed distance; resolving sets; dimension
UR - http://eudml.org/doc/248478
ER -

References

top
  1. G. Chartrand L. Eroh M. Johnson O. R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Preprint. MR1780464
  2. F. Harary R. A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976), 191-195. (1976) MR0457289
  3. P. J. Slater, Leaves of trees, Congress. Numer. 11, (1975), 549-559. (1975) Zbl0316.05102MR0422062
  4. P. J. Slater, Dominating and reference sets in graphs, J. Math. Phys. Sci. 22 (1988), 445-455. (1988) MR0966610

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.