Connected resolvability of graphs

Title:

Connected resolvability of graphs

Creator:

Saenpholphat, Varaporn and Zhang, Ping

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:5aee80ee-5175-4270-8d0a-011a5c2cac66
uuid:5aee80ee-5175-4270-8d0a-011a5c2cac66

Subject:

resolving set, basis, dimension, connected resolving set, and connected resolving number

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

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.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

827-840

Source:

Czechoslovak Mathematical Journal | 2003 Volume:53 | Number:4

Harvested from:

CDK

Metadata only:

false