Connected resolving decompositions in graphs

Saenpholphat, Varaporn ; Zhang, Ping

Mathematica Bohemica, Tome 128 (2003) no. 2, pp. 121-136.

Résumé

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 cd}(G)$. Thus $2 \le \dim _{\text{d}}(G) \le \mathop {\mathrm cd}(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 cd}(G) = b$.

Détail

DOI : 10.21136/MB.2003.134033

Classification : 05C12
Keywords: distance; resolving decomposition; connected resolving decomposition