| Title:
|
The independent resolving number of a graph (English) |
| Author:
|
Chartrand, G. |
| Author:
|
Saenpholphat, V. |
| Author:
|
Zhang, P. |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
128 |
| Issue:
|
4 |
| Year:
|
2003 |
| Pages:
|
379-393 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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$. (English) |
| Keyword:
|
distance |
| Keyword:
|
resolving set |
| Keyword:
|
independent set |
| MSC:
|
05C12 |
| MSC:
|
05C69 |
| idZBL:
|
Zbl 1050.05043 |
| idMR:
|
MR2032475 |
| DOI:
|
10.21136/MB.2003.134003 |
| . |
| Date available:
|
2009-09-24T22:10:59Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/134003 |
| . |
| Reference:
|
[1] F. Buckley, F. Harary: Distance in Graphs.Addison-Wesley, Redwood City, CA, 1990. MR 1045632 |
| Reference:
|
[2] G. Chartrand, L. Lesniak: Graphs $\&$ Digraphs, third edition.CRC Press, Boca Raton, 1996. MR 1408678 |
| Reference:
|
[3] F. Harary, R. A. Melter: On the metric dimension of a graph.Ars Combin. 2 (1976), 191–195. MR 0457289 |
| Reference:
|
[4] P. J. Slater: Leaves of trees.Congress. Numer. 14 (1975), 549–559. Zbl 0316.05102, MR 0422062 |
| Reference:
|
[5] P. J. Slater: Dominating and reference sets in graphs.J. Math. Phys. Sci. 22 (1988), 445–455. MR 0966610 |
| . |
