Connected resolvability of graphs

Varaporn Saenpholphat; Ping Zhang

Czechoslovak Mathematical Journal (2003)

  • Volume: 53, Issue: 4, page 827-840
  • ISSN: 0011-4642

Abstract

top
For an ordered set W = { w 1 , w 2 , ⋯ , w k } 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 ) , ⋯ , 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 c r ( G ) . Thus 1 ≤ dim ( G ) ≤ c r ( G ) ≤ n - 1 for every connected graph G of order n ≥ 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 ≥ 3 , then c r ( 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 ≤ b , there exists a connected graph G with dim ( G ) = a and c r ( G ) = b if and only if ( a , b ) ∉ { ( 1 , k ) k = 1 or k ≥ 3 } . Several other realization results are present. The connected resolving numbers of the Cartesian products G × K 2 for connected graphs G are studied.

How to cite

top

Saenpholphat, Varaporn, and Zhang, Ping. "Connected resolvability of graphs." Czechoslovak Mathematical Journal 53.4 (2003): 827-840. <http://eudml.org/doc/30818>.

@article{Saenpholphat2003,
abstract = {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 \{c\}r\}(G)$. Thus $1 \le \dim (G) \le \mathop \{\mathrm \{c\}r\}(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 \{c\}r\}(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 \{c\}r\}(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.},
author = {Saenpholphat, Varaporn, Zhang, Ping},
journal = {Czechoslovak Mathematical Journal},
keywords = {resolving set; basis; dimension; connected resolving set; connected resolving number; basis; dimension; connected resolving set; connected resolving number},
language = {eng},
number = {4},
pages = {827-840},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Connected resolvability of graphs},
url = {http://eudml.org/doc/30818},
volume = {53},
year = {2003},
}

TY - JOUR
AU - Saenpholphat, Varaporn
AU - Zhang, Ping
TI - Connected resolvability of graphs
JO - Czechoslovak Mathematical Journal
PY - 2003
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 53
IS - 4
SP - 827
EP - 840
AB - 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 {c}r}(G)$. Thus $1 \le \dim (G) \le \mathop {\mathrm {c}r}(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 {c}r}(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 {c}r}(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.
LA - eng
KW - resolving set; basis; dimension; connected resolving set; connected resolving number; basis; dimension; connected resolving set; connected resolving number
UR - http://eudml.org/doc/30818
ER -

References

top
  1. 10.1023/A:1025745406160, Period. Math. Hungar. 46 (2003), 25–36. (2003) MR1975342DOI10.1023/A:1025745406160
  2. 10.1016/S0166-218X(00)00198-0, Discrete Appl. Math. 105 (2000), 99–113. (2000) MR1780464DOI10.1016/S0166-218X(00)00198-0
  3. Graphs & Digraphs. Third edition, Chapman Hall, New York, 1996. (1996) MR1408678
  4. Resolvability and the upper dimension of graphs, Inter. J. Comput. Math. Appl. 39 (2000), 19–28. (2000) MR1763834
  5. The directed distance dimension of oriented graphs, Math. Bohem. 125 (2000), 155–168. (2000) MR1768804
  6. Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979. (1979) MR0519066
  7. On the metric dimension of a graph, Ars Combin. 2 (1976), 191–195. (1976) MR0457289
  8. Browsable structure-activity datasets, Submitted. 
  9. Leaves of trees, Congr. Numer. 14 (1975), 549–559. (1975) Zbl0316.05102MR0422062
  10. Dominating and reference sets in graphs, J.  Math. Phys. Sci. 22 (1988), 445–455. (1988) MR0966610

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.