On connected resolving decompositions in graphs

Saenpholphat, Varaporn, and Zhang, Ping. "On connected resolving decompositions in graphs." Czechoslovak Mathematical Journal 54.3 (2004): 681-696. <http://eudml.org/doc/30891>.

@article{Saenpholphat2004,
abstract = {For an ordered $k$-decomposition $\mathcal \{D\} = \lbrace G_1, G_2,\dots , 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 _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 _d(G) \le \mathop \{\mathrm \{c\}d\}(G) \le m$ for every connected graph $G$ of size $m \ge 2$. All nontrivial connected graphs of size $m$ with connected decomposition number 2 or $m$ have been characterized. We present characterizations for connected graphs of size $m$ with connected decomposition number $m-1$ or $m-2$. It is shown that each pair $s, t$ of rational numbers with $ 0 < s \le t \le 1$, there is a connected graph $G$ of size $m$ such that $\dim _d(G)/m = s$ and $\mathop \{\mathrm \{c\}d\}(G) / m = t$.},
author = {Saenpholphat, Varaporn, Zhang, Ping},
journal = {Czechoslovak Mathematical Journal},
keywords = {distance; resolving decomposition; connected resolving decomposition; distance; resolving decomposition; connected resolving decomposition},
language = {eng},
number = {3},
pages = {681-696},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On connected resolving decompositions in graphs},
url = {http://eudml.org/doc/30891},
volume = {54},
year = {2004},
}

TY - JOUR
AU - Saenpholphat, Varaporn
AU - Zhang, Ping
TI - On connected resolving decompositions in graphs
JO - Czechoslovak Mathematical Journal
PY - 2004
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 54
IS - 3
SP - 681
EP - 696
AB - For an ordered $k$-decomposition $\mathcal {D} = \lbrace G_1, G_2,\dots , 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 _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 _d(G) \le \mathop {\mathrm {c}d}(G) \le m$ for every connected graph $G$ of size $m \ge 2$. All nontrivial connected graphs of size $m$ with connected decomposition number 2 or $m$ have been characterized. We present characterizations for connected graphs of size $m$ with connected decomposition number $m-1$ or $m-2$. It is shown that each pair $s, t$ of rational numbers with $ 0 < s \le t \le 1$, there is a connected graph $G$ of size $m$ such that $\dim _d(G)/m = s$ and $\mathop {\mathrm {c}d}(G) / m = t$.
LA - eng
KW - distance; resolving decomposition; connected resolving decomposition; distance; resolving decomposition; connected resolving decomposition
UR - http://eudml.org/doc/30891
ER -