# Connected resolving decompositions in graphs

Varaporn Saenpholphat; Ping Zhang

Mathematica Bohemica (2003)

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

## Access Full Article

top## Abstract

top## How to cite

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

## Citations in EuDML Documents

top## NotesEmbed ?

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