Connected resolving decompositions in graphs

Saenpholphat, Varaporn, and Zhang, Ping. "Connected resolving decompositions in graphs." Mathematica Bohemica 128.2 (2003): 121-136. <http://eudml.org/doc/249230>.

@article{Saenpholphat2003,
abstract = {For an ordered $k$-decomposition $\{\mathcal \{D\}\}= \lbrace G_1, G_2,\ldots , G_k\rbrace $ of a connected graph $G$ and an edge $e$ of $G$, the $\{\mathcal \{D\}\}$-code of $e$ is the $k$-tuple $c_\{\{\mathcal \{D\}\}\}(e)$ = ($d(e, G_1),$$d(e, G_2),$$\ldots ,$$d(e, G_k)$), where $d(e, G_i)$ is the distance from $e$ to $G_i$. A decomposition $\{\mathcal \{D\}\}$ is resolving if every two distinct edges of $G$ have distinct $\{\mathcal \{D\}\}$-codes. The minimum $k$ for which $G$ has a resolving $k$-decomposition is its decomposition dimension $\dim _\{\text\{d\}\}(G)$. A resolving decomposition $\{\mathcal \{D\}\}$ of $G$ is connected if each $G_i$ is connected for $1 \le i \le k$. The minimum $k$ for which $G$ has a connected resolving $k$-decomposition is its connected decomposition number $\mathop \{\mathrm \{c\}d\}(G)$. Thus $2 \le \dim _\{\text\{d\}\}(G) \le \mathop \{\mathrm \{c\}d\}(G) \le m$ for every connected graph $G$ of size $m \ge 2$. All nontrivial connected graphs with connected decomposition number $2$ or $m$ are characterized. We provide bounds for the connected decomposition number of a connected graph in terms of its size, diameter, girth, and other parameters. A formula for the connected decomposition number of a nonpath tree is established. It is shown that, for every pair $a, b$ of integers with $3 \le a \le b$, there exists a connected graph $G$ with $\dim _\{\text\{d\}\}(G) = a$ and $\mathop \{\mathrm \{c\}d\}(G) = b$.},
author = {Saenpholphat, Varaporn, Zhang, Ping},
journal = {Mathematica Bohemica},
keywords = {distance; resolving decomposition; connected resolving decomposition; distance; resolving decomposition; connected resolving decomposition},
language = {eng},
number = {2},
pages = {121-136},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Connected resolving decompositions in graphs},
url = {http://eudml.org/doc/249230},
volume = {128},
year = {2003},
}

TY - JOUR
AU - Saenpholphat, Varaporn
AU - Zhang, Ping
TI - Connected resolving decompositions in graphs
JO - Mathematica Bohemica
PY - 2003
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 128
IS - 2
SP - 121
EP - 136
AB - For an ordered $k$-decomposition ${\mathcal {D}}= \lbrace G_1, G_2,\ldots , G_k\rbrace $ of a connected graph $G$ and an edge $e$ of $G$, the ${\mathcal {D}}$-code of $e$ is the $k$-tuple $c_{{\mathcal {D}}}(e)$ = ($d(e, G_1),$$d(e, G_2),$$\ldots ,$$d(e, G_k)$), where $d(e, G_i)$ is the distance from $e$ to $G_i$. A decomposition ${\mathcal {D}}$ is resolving if every two distinct edges of $G$ have distinct ${\mathcal {D}}$-codes. The minimum $k$ for which $G$ has a resolving $k$-decomposition is its decomposition dimension $\dim _{\text{d}}(G)$. A resolving decomposition ${\mathcal {D}}$ of $G$ is connected if each $G_i$ is connected for $1 \le i \le k$. The minimum $k$ for which $G$ has a connected resolving $k$-decomposition is its connected decomposition number $\mathop {\mathrm {c}d}(G)$. Thus $2 \le \dim _{\text{d}}(G) \le \mathop {\mathrm {c}d}(G) \le m$ for every connected graph $G$ of size $m \ge 2$. All nontrivial connected graphs with connected decomposition number $2$ or $m$ are characterized. We provide bounds for the connected decomposition number of a connected graph in terms of its size, diameter, girth, and other parameters. A formula for the connected decomposition number of a nonpath tree is established. It is shown that, for every pair $a, b$ of integers with $3 \le a \le b$, there exists a connected graph $G$ with $\dim _{\text{d}}(G) = a$ and $\mathop {\mathrm {c}d}(G) = b$.
LA - eng
KW - distance; resolving decomposition; connected resolving decomposition; distance; resolving decomposition; connected resolving decomposition
UR - http://eudml.org/doc/249230
ER -