| Title:
|
Connected resolving decompositions in graphs (English) |
| Author:
|
Saenpholphat, Varaporn |
| Author:
|
Zhang, Ping |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
128 |
| Issue:
|
2 |
| Year:
|
2003 |
| Pages:
|
121-136 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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$. (English) |
| Keyword:
|
distance |
| Keyword:
|
resolving decomposition |
| Keyword:
|
connected resolving decomposition |
| MSC:
|
05C12 |
| idZBL:
|
Zbl 1021.05030 |
| idMR:
|
MR1995567 |
| DOI:
|
10.21136/MB.2003.134033 |
| . |
| Date available:
|
2009-09-24T22:07:48Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/134033 |
| . |
| Reference:
|
[1] J. Bosák: Decompositions of Graphs.Kluwer Academic, Boston, 1990. MR 1071373 |
| Reference:
|
[2] G. Chartrand, D. Erwin, M. Raines, P. Zhang: The decomposition dimension of graphs.Graphs Combin. 17 (2001), 599–605. MR 1876570, 10.1007/PL00007252 |
| Reference:
|
[3] G. Chartrand, L. Lesniak: Graphs $\&$ Digraphs, third edition.Chapman $\&$ Hall, New York, 1996. MR 1408678 |
| Reference:
|
[4] H. Enomoto, T. Nakamigawa: On the decomposition dimension of trees.Preprint. MR 1907757 |
| Reference:
|
[5] A. Küngen, D. B. West: Decomposition dimension of graphs and union-free family of sets.Preprint. |
| Reference:
|
[6] M. A. Johnson: Structure-activity maps for visualizing the graph variables arising in drug design.J. Biopharm. Statist. 3 (1993), 203–236. Zbl 0800.92106, 10.1080/10543409308835060 |
| Reference:
|
[7] M. A. Johnson: Browsable structure-activity datasets.Preprint. |
| Reference:
|
[8] F. Harary, R. A. Melter: On the metric dimension of a graph.Ars Combin. 2 (1976), 191–195. MR 0457289 |
| Reference:
|
[9] P. J. Slater: Leaves of trees.Congress. Numer. 14 (1975), 549–559. Zbl 0316.05102, MR 0422062 |
| Reference:
|
[10] P. J. Slater: Dominating and reference sets in graphs.J. Math. Phys. Sci. 22 (1988), 445–455. MR 0966610 |
| . |
