MATHEMATICA BOHEMICA, Vol. 128, No. 2, pp. 121-136 (2003)

Connected resolving decompositions in graphs

Varaporn Saenpholphat, Ping Zhang

Varaporn Saenpholphat, Ping Zhang, Department of Mathematics and Statistics, Western Michigan University, Kalamazoo, MI 49008, USA, e-mails:,

Abstract: For an ordered $k$-decomposition $\cD= \{G_1, G_2,\ldots, G_k\}$ of a connected graph $G$ and an edge $e$ of $G$, the $\cD$-code of $e$ is the $k$-tuple $c_{\cD}(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 $\cD$ is resolving if every two distinct edges of $G$ have distinct $\cD$-codes. The minimum $k$ for which $G$ has a resolving $k$-decomposition is its decomposition dimension $\dim_{\d}(G)$. A resolving decomposition $\cD$ of $G$ is connected if each $G_i$ is connected for $1 \leq i \leq k$. The minimum $k$ for which $G$ has a connected resolving $k$-decomposition is its connected decomposition number $\cd(G)$. Thus $2 \leq\dim_{\d}(G) \leq\cd(G) \leq m$ for every connected graph $G$ of size $m \geq2$. 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 \leq a \leq b$, there exists a connected graph $G$ with $\dim_{\d}(G) = a$ and $\cd(G) = b$.

Keywords: distance, resolving decomposition, connected resolving decomposition

Classification (MSC2000): 05C12

Full text of the article:

[Previous Article] [Next Article] [Contents of this Number] [Journals Homepage]
© 2004–2010 FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition