| Title:
|
On connected resolving decompositions in graphs (English) |
| Author:
|
Saenpholphat, Varaporn |
| Author:
|
Zhang, Ping |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
54 |
| Issue:
|
3 |
| Year:
|
2004 |
| Pages:
|
681-696 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
For an ordered $k$-decomposition $\mathcal D = \lbrace G_1, G_2,\dots , 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 _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 _d(G) \le \mathop {\mathrm cd}(G) \le m$ for every connected graph $G$ of size $m \ge 2$. All nontrivial connected graphs of size $m$ with connected decomposition number 2 or $m$ have been characterized. We present characterizations for connected graphs of size $m$ with connected decomposition number $m-1$ or $m-2$. It is shown that each pair $s, t$ of rational numbers with $ 0 < s \le t \le 1$, there is a connected graph $G$ of size $m$ such that $\dim _d(G)/m = s$ and $\mathop {\mathrm cd}(G) / m = t$. (English) |
| Keyword:
|
distance |
| Keyword:
|
resolving decomposition |
| Keyword:
|
connected resolving decomposition |
| MSC:
|
05C12 |
| MSC:
|
05C40 |
| idZBL:
|
Zbl 1080.05508 |
| idMR:
|
MR2086725 |
| . |
| Date available:
|
2009-09-24T11:16:28Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127920 |
| . |
| Reference:
|
[1] J. Bosak: Decompositions of Graphs.Kluwer Academic, Boston, 1990. Zbl 0701.05042, MR 1071373 |
| Reference:
|
[2] G. Chartrand, D. Erwin, M. Raines and P. Zhang: The decomposition dimension of graphs.Graphs and Combin. 17 (2001), 599–605. MR 1876570, 10.1007/PL00007252 |
| Reference:
|
[3] G. Chartrand and L. Lesniak: Graphs & Digraphs, third edition.Chapman & Hall, New York, 1996. MR 1408678 |
| Reference:
|
[4] H. Enomoto and T. Nakamigawa: On the decomposition dimension of trees.Discrete Math. 252 (2002), 219–225. MR 1907757, 10.1016/S0012-365X(01)00454-X |
| Reference:
|
[5] A. Küngen and D. B. West: Decomposition dimension of graphs and a 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 and R. A. Melter: On the metric dimension of a graph.Ars Combin. 2 (1976), 191–195. MR 0457289 |
| Reference:
|
[9] B. L. Hulme, A. W. Shiver and P. J. Slater: FIRE: A subroutine for fire protection network analysis.SAND 81-1261, Sandia National Laboratories, Albuquerque, 1981. |
| Reference:
|
[10] B. L. Hulme, A. W. Shiver and P. J. Slater: Computing minimum cost fire protection.SAND 82-0809, Sandia National Laboratories, Albuquerque, 1982. |
| Reference:
|
[11] B. L. Hulme, A. W. Shiver and P. J. Slater: A Boolean algebraic analysis of fire protection.Annals of Discrete Mathematics, Algebraic Structure in Operations Research, 1984, pp. 215–228. MR 0780023 |
| Reference:
|
[12] P. J. Slater: Leaves of trees.Congr. Numer. 14 (1975), 549–559. Zbl 0316.05102, MR 0422062 |
| Reference:
|
[13] P. J. Slater: Dominating and reference sets in graphs.J. Math. Phys. Sci. 22 (1988), 445–455. MR 0966610 |
| Reference:
|
[14] V. Saenpholphat and P. Zhang: Connected resolving decompositions in graphs.Math. Bohem. 128 (2003), 121–136. MR 1995567 |
| . |
