Geodesic
Connected resolvability of graphs
Czechoslovak Mathematical Journal, Tome 53 (2003) no. 4, pp. 827-840
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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 $$ 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.
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 $$
Classification : 05C12, 05C25, 05C35
Keywords: resolving set; basis; dimension; connected resolving set; connected resolving number 
@article{CMJ_2003_53_4_a4,
     author = {Saenpholphat, Varaporn and Zhang, Ping},
     title = {Connected resolvability of graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {827--840},
     year = {2003},
     volume = {53},
     number = {4},
     mrnumber = {2018833},
     zbl = {1080.05507},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2003_53_4_a4/}
}
TY  - JOUR
AU  - Saenpholphat, Varaporn
AU  - Zhang, Ping
TI  - Connected resolvability of graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2003
SP  - 827
EP  - 840
VL  - 53
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/CMJ_2003_53_4_a4/
LA  - en
ID  - CMJ_2003_53_4_a4
ER  - 
%0 Journal Article
%A Saenpholphat, Varaporn
%A Zhang, Ping
%T Connected resolvability of graphs
%J Czechoslovak Mathematical Journal
%D 2003
%P 827-840
%V 53
%N 4
%U http://geodesic.mathdoc.fr/item/CMJ_2003_53_4_a4/
%G en
%F CMJ_2003_53_4_a4
Saenpholphat, Varaporn; Zhang, Ping. Connected resolvability of graphs. Czechoslovak Mathematical Journal, Tome 53 (2003) no. 4, pp. 827-840. http://geodesic.mathdoc.fr/item/CMJ_2003_53_4_a4/

[1] P.  Buczkowski, G.  Chartrand, C.  Poisson and P. Zhang: On $k$-dimensional graphs and their bases. Period. Math. Hungar. 46 (2003), 25–36. | DOI | MR

[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. | DOI | MR

[3] G.  Chartrand and L.  Lesniak: Graphs $\&$ Digraphs. Third edition. Chapman $\&$ Hall, New York, 1996. | MR

[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

[5] G.  Chartrand, M.  Raines and P. Zhang: The directed distance dimension of oriented graphs. Math. Bohem. 125 (2000), 155–168. | MR

[6] M. R.  Garey and D. S.  Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979. | MR

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

[8] M. A.  Johnson: Browsable structure-activity datasets. Submitted.

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

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