The local metric dimension of a graph

Okamoto, Futaba, Phinezy, Bryan, and Zhang, Ping. "The local metric dimension of a graph." Mathematica Bohemica 135.3 (2010): 239-255. <http://eudml.org/doc/38128>.

@article{Okamoto2010,
abstract = {For an ordered set $W= \lbrace w_1,w_2,\ldots ,w_k\rbrace $ of $k$ distinct vertices in a nontrivial connected graph $G$, the metric code of a vertex $v$ of $G$ with respect to $W$ is the $k$-vector \[ \mathop \{\rm code\}(v)= ( d(v,w\_1),d(v,w\_2),\cdots ,d(v,w\_k) ) \] where $d(v,w_i)$ is the distance between $v$ and $w_i$ for $1\le i\le k$. The set $W$ is a local metric set of $G$ if $\mathop \{\rm code\}(u)\ne \mathop \{\rm code\}(v)$ for every pair $u,v$ of adjacent vertices of $G$. The minimum positive integer $k$ for which $G$ has a local metric $k$-set is the local metric dimension $\mathop \{\rm lmd\}(G)$ of $G$. A local metric set of $G$ of cardinality $\mathop \{\rm lmd\}(G)$ is a local metric basis of $G$. We characterize all nontrivial connected graphs of order $n$ having local metric dimension $1$, $n-2$, or $n-1$ and establish sharp bounds for the local metric dimension of a graph in terms of well-known graphical parameters. Several realization results are presented along with other results on the number of local metric bases of a connected graph.},
author = {Okamoto, Futaba, Phinezy, Bryan, Zhang, Ping},
journal = {Mathematica Bohemica},
keywords = {distance; local metric set; local metric dimension; distance; local metric set; local metric dimension},
language = {eng},
number = {3},
pages = {239-255},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {The local metric dimension of a graph},
url = {http://eudml.org/doc/38128},
volume = {135},
year = {2010},
}

TY - JOUR
AU - Okamoto, Futaba
AU - Phinezy, Bryan
AU - Zhang, Ping
TI - The local metric dimension of a graph
JO - Mathematica Bohemica
PY - 2010
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 135
IS - 3
SP - 239
EP - 255
AB - For an ordered set $W= \lbrace w_1,w_2,\ldots ,w_k\rbrace $ of $k$ distinct vertices in a nontrivial connected graph $G$, the metric code of a vertex $v$ of $G$ with respect to $W$ is the $k$-vector \[ \mathop {\rm code}(v)= ( d(v,w_1),d(v,w_2),\cdots ,d(v,w_k) ) \] where $d(v,w_i)$ is the distance between $v$ and $w_i$ for $1\le i\le k$. The set $W$ is a local metric set of $G$ if $\mathop {\rm code}(u)\ne \mathop {\rm code}(v)$ for every pair $u,v$ of adjacent vertices of $G$. The minimum positive integer $k$ for which $G$ has a local metric $k$-set is the local metric dimension $\mathop {\rm lmd}(G)$ of $G$. A local metric set of $G$ of cardinality $\mathop {\rm lmd}(G)$ is a local metric basis of $G$. We characterize all nontrivial connected graphs of order $n$ having local metric dimension $1$, $n-2$, or $n-1$ and establish sharp bounds for the local metric dimension of a graph in terms of well-known graphical parameters. Several realization results are presented along with other results on the number of local metric bases of a connected graph.
LA - eng
KW - distance; local metric set; local metric dimension; distance; local metric set; local metric dimension
UR - http://eudml.org/doc/38128
ER -