Geodesic
The independent resolving number of a graph
Mathematica Bohemica, Tome 128 (2003) no. 4, pp. 379-393

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

MR Zbl
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 ir}(G)$. We study the existence of independent resolving sets in graphs, characterize all nontrivial connected graphs $G$ of order $n$ with $\mathop {\mathrm ir}(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 ir}(G) = k$ such that exactly $r$ vertices belong to every minimum independent resolving set of $G$.
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 ir}(G)$. We study the existence of independent resolving sets in graphs, characterize all nontrivial connected graphs $G$ of order $n$ with $\mathop {\mathrm ir}(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 ir}(G) = k$ such that exactly $r$ vertices belong to every minimum independent resolving set of $G$.
DOI : 10.21136/MB.2003.134003
Classification : 05C12, 05C69
Keywords: distance; resolving set; independent set 
Chartrand, G.; Saenpholphat, V.; Zhang, P. The independent resolving number of a graph. Mathematica Bohemica, Tome 128 (2003) no. 4, pp. 379-393. doi: 10.21136/MB.2003.134003
@article{10_21136_MB_2003_134003,
     author = {Chartrand, G. and Saenpholphat, V. and Zhang, P.},
     title = {The independent resolving number of a graph},
     journal = {Mathematica Bohemica},
     pages = {379--393},
     year = {2003},
     volume = {128},
     number = {4},
     doi = {10.21136/MB.2003.134003},
     mrnumber = {2032475},
     zbl = {1050.05043},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2003.134003/}
}
TY  - JOUR
AU  - Chartrand, G.
AU  - Saenpholphat, V.
AU  - Zhang, P.
TI  - The independent resolving number of a graph
JO  - Mathematica Bohemica
PY  - 2003
SP  - 379
EP  - 393
VL  - 128
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2003.134003/
DO  - 10.21136/MB.2003.134003
LA  - en
ID  - 10_21136_MB_2003_134003
ER  - 
%0 Journal Article
%A Chartrand, G.
%A Saenpholphat, V.
%A Zhang, P.
%T The independent resolving number of a graph
%J Mathematica Bohemica
%D 2003
%P 379-393
%V 128
%N 4
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2003.134003/
%R 10.21136/MB.2003.134003
%G en
%F 10_21136_MB_2003_134003

[1] F. Buckley, F. Harary: Distance in Graphs. Addison-Wesley, Redwood City, CA, 1990. | MR

[2] G. Chartrand, L. Lesniak: Graphs $\&$ Digraphs, third edition. CRC Press, Boca Raton, 1996. | MR

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

[4] P. J. Slater: Leaves of trees. Congress. Numer. 14 (1975), 549–559. | MR | Zbl

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

Cité par Sources :