# Connected resolving decompositions in graphs

Mathematica Bohemica (2003)

• Volume: 128, Issue: 2, page 121-136
• ISSN: 0862-7959

top

## Abstract

top
For an ordered $k$-decomposition $𝒟=\left\{{G}_{1},{G}_{2},...,{G}_{k}\right\}$ of a connected graph $G$ and an edge $e$ of $G$, the $𝒟$-code of $e$ is the $k$-tuple ${c}_{𝒟}\left(e\right)$ = ($d\left(e,{G}_{1}\right),$$d\left(e,{G}_{2}\right),$$...,$$d\left(e,{G}_{k}\right)$), where $d\left(e,{G}_{i}\right)$ is the distance from $e$ to ${G}_{i}$. A decomposition $𝒟$ is resolving if every two distinct edges of $G$ have distinct $𝒟$-codes. The minimum $k$ for which $G$ has a resolving $k$-decomposition is its decomposition dimension ${dim}_{\text{d}}\left(G\right)$. A resolving decomposition $𝒟$ 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 $\mathrm{c}d\left(G\right)$. Thus $2\le {dim}_{\text{d}}\left(G\right)\le \mathrm{c}d\left(G\right)\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}}\left(G\right)=a$ and $\mathrm{c}d\left(G\right)=b$.

## How to cite

top

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 -

## References

top
1. Decompositions of Graphs, Kluwer Academic, Boston, 1990. (1990) MR1071373
2. 10.1007/PL00007252, Graphs Combin. 17 (2001), 599–605. (2001) MR1876570DOI10.1007/PL00007252
3. Graphs $&$ Digraphs, third edition, Chapman Hall, New York, 1996. (1996) MR1408678
4. On the decomposition dimension of trees, Preprint. MR1907757
5. Decomposition dimension of graphs and union-free family of sets, Preprint.
6. 10.1080/10543409308835060, J. Biopharm. Statist. 3 (1993), 203–236. (1993) Zbl0800.92106DOI10.1080/10543409308835060
7. Browsable structure-activity datasets, Preprint.
8. On the metric dimension of a graph, Ars Combin. 2 (1976), 191–195. (1976) MR0457289
9. Leaves of trees, Congress. Numer. 14 (1975), 549–559. (1975) Zbl0316.05102MR0422062
10. Dominating and reference sets in graphs, J. Math. Phys. Sci. 22 (1988), 445–455. (1988) MR0966610

top

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.