The independent resolving number of a graph

Chartrand, Gary, Saenpholphat, Varaporn, and Zhang, Ping. "The independent resolving number of a graph." Mathematica Bohemica 128.4 (2003): 379-393. <http://eudml.org/doc/249220>.

@article{Chartrand2003,
abstract = {For an ordered set $W=\lbrace w_1, w_2, \dots , w_k\rbrace $ of vertices in a connected graph $G$ and a vertex $v$ of $G$, the code of $v$ with respect to $W$ is the $k$-vector \[ c\_W(v) = (d(v, w\_1), d(v, w\_2), \dots , d(v, w\_k) ). \] The set $W$ is an independent resolving set for $G$ if (1) $W$ is independent in $G$ and (2) distinct vertices have distinct codes with respect to $W$. The cardinality of a minimum independent resolving set in $G$ is the independent resolving number $\mathop \{\mathrm \{i\}r\}(G)$. We study the existence of independent resolving sets in graphs, characterize all nontrivial connected graphs $G$ of order $n$ with $\mathop \{\mathrm \{i\}r\}(G) = 1$, $n-1$, $n-2$, and present several realization results. It is shown that for every pair $r, k$ of integers with $k \ge 2$ and $0 \le r \le k$, there exists a connected graph $G$ with $\mathop \{\mathrm \{i\}r\}(G) = k$ such that exactly $r$ vertices belong to every minimum independent resolving set of $G$.},
author = {Chartrand, Gary, Saenpholphat, Varaporn, Zhang, Ping},
journal = {Mathematica Bohemica},
keywords = {distance; resolving set; independent set; distance; resolving set; independent set},
language = {eng},
number = {4},
pages = {379-393},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {The independent resolving number of a graph},
url = {http://eudml.org/doc/249220},
volume = {128},
year = {2003},
}

TY - JOUR
AU - Chartrand, Gary
AU - Saenpholphat, Varaporn
AU - Zhang, Ping
TI - The independent resolving number of a graph
JO - Mathematica Bohemica
PY - 2003
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 128
IS - 4
SP - 379
EP - 393
AB - For an ordered set $W=\lbrace w_1, w_2, \dots , w_k\rbrace $ of vertices in a connected graph $G$ and a vertex $v$ of $G$, the code of $v$ with respect to $W$ is the $k$-vector \[ c_W(v) = (d(v, w_1), d(v, w_2), \dots , d(v, w_k) ). \] The set $W$ is an independent resolving set for $G$ if (1) $W$ is independent in $G$ and (2) distinct vertices have distinct codes with respect to $W$. The cardinality of a minimum independent resolving set in $G$ is the independent resolving number $\mathop {\mathrm {i}r}(G)$. We study the existence of independent resolving sets in graphs, characterize all nontrivial connected graphs $G$ of order $n$ with $\mathop {\mathrm {i}r}(G) = 1$, $n-1$, $n-2$, and present several realization results. It is shown that for every pair $r, k$ of integers with $k \ge 2$ and $0 \le r \le k$, there exists a connected graph $G$ with $\mathop {\mathrm {i}r}(G) = k$ such that exactly $r$ vertices belong to every minimum independent resolving set of $G$.
LA - eng
KW - distance; resolving set; independent set; distance; resolving set; independent set
UR - http://eudml.org/doc/249220
ER -