| Title:
|
Connected resolvability of graphs (English) |
| Author:
|
Saenpholphat, Varaporn |
| Author:
|
Zhang, Ping |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
53 |
| Issue:
|
4 |
| Year:
|
2003 |
| Pages:
|
827-840 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
For an ordered set $W=\lbrace w_1, w_2, \dots , w_k\rbrace $ of vertices and a vertex $v$ in a connected graph $G$, the representation of $v$ with respect to $W$ is the $k$-vector $r(v|W)$ = ($d(v, w_1)$, $d(v, w_2),\dots ,d(v, w_k))$, where $d(x,y)$ represents the distance between the vertices $x$ and $y$. The set $W$ is a resolving set for $G$ if distinct vertices of $G$ have distinct representations with respect to $W$. A resolving set for $G$ containing a minimum number of vertices is a basis for $G$. The dimension $\dim (G)$ is the number of vertices in a basis for $G$. A resolving set $W$ of $G$ is connected if the subgraph $<W>$ induced by $W$ is a nontrivial connected subgraph of $G$. The minimum cardinality of a connected resolving set in a graph $G$ is its connected resolving number $\mathop {\mathrm cr}(G)$. Thus $1 \le \dim (G) \le \mathop {\mathrm cr}(G) \le n-1$ for every connected graph $G$ of order $n \ge 3$. The connected resolving numbers of some well-known graphs are determined. It is shown that if $G$ is a connected graph of order $n \ge 3$, then $\mathop {\mathrm cr}(G) = n-1$ if and only if $G = K_n$ or $G = K_{1, n-1}$. It is also shown that for positive integers $a$, $b$ with $a \le b$, there exists a connected graph $G$ with $\dim (G) = a$ and $\mathop {\mathrm cr}(G) = b$ if and only if $(a, b) \notin \lbrace (1, k)\: k = 1\hspace{5.0pt}\text{or}\hspace{5.0pt}k \ge 3\rbrace $. Several other realization results are present. The connected resolving numbers of the Cartesian products $G \times K_2$ for connected graphs $G$ are studied. (English) |
| Keyword:
|
resolving set |
| Keyword:
|
basis |
| Keyword:
|
dimension |
| Keyword:
|
connected resolving set |
| Keyword:
|
connected resolving number |
| MSC:
|
05C12 |
| MSC:
|
05C25 |
| MSC:
|
05C35 |
| idZBL:
|
Zbl 1080.05507 |
| idMR:
|
MR2018833 |
| . |
| Date available:
|
2009-09-24T11:06:59Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127843 |
| . |
| Reference:
|
[1] P. Buczkowski, G. Chartrand, C. Poisson and P. Zhang: On $k$-dimensional graphs and their bases.Period. Math. Hungar. 46 (2003), 25–36. MR 1975342, 10.1023/A:1025745406160 |
| Reference:
|
[2] G. Chartrand, L. Eroh, M. Johnson and O. Oellermann: Resolvability in graphs and the metric dimension of a graph.Discrete Appl. Math. 105 (2000), 99–113. MR 1780464, 10.1016/S0166-218X(00)00198-0 |
| Reference:
|
[3] G. Chartrand and L. Lesniak: Graphs $\&$ Digraphs. Third edition.Chapman $\&$ Hall, New York, 1996. MR 1408678 |
| Reference:
|
[4] G. Chartrand, C. Poisson and P. Zhang: Resolvability and the upper dimension of graphs.Inter. J. Comput. Math. Appl. 39 (2000), 19–28. MR 1763834 |
| Reference:
|
[5] G. Chartrand, M. Raines and P. Zhang: The directed distance dimension of oriented graphs.Math. Bohem. 125 (2000), 155–168. MR 1768804 |
| Reference:
|
[6] M. R. Garey and D. S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness.Freeman, New York, 1979. MR 0519066 |
| Reference:
|
[7] F. Harary and R. A. Melter: On the metric dimension of a graph.Ars Combin. 2 (1976), 191–195. MR 0457289 |
| Reference:
|
[8] M. A. Johnson: Browsable structure-activity datasets.Submitted. |
| Reference:
|
[9] P. J. Slater: Leaves of trees.Congr. Numer. 14 (1975), 549–559. Zbl 0316.05102, MR 0422062 |
| Reference:
|
[10] P. J. Slater: Dominating and reference sets in graphs.J. Math. Phys. Sci. 22 (1988), 445–455. MR 0966610 |
| . |
