Geodesic
On connected resolving decompositions in graphs
Czechoslovak Mathematical Journal, Tome 54 (2004) no. 3, pp. 681-696
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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$.
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$.
Classification : 05C12, 05C40
Keywords: distance; resolving decomposition; connected resolving decomposition 
@article{CMJ_2004_54_3_a10,
     author = {Saenpholphat, Varaporn and Zhang, Ping},
     title = {On connected resolving decompositions in graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {681--696},
     year = {2004},
     volume = {54},
     number = {3},
     mrnumber = {2086725},
     zbl = {1080.05508},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2004_54_3_a10/}
}
TY  - JOUR
AU  - Saenpholphat, Varaporn
AU  - Zhang, Ping
TI  - On connected resolving decompositions in graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2004
SP  - 681
EP  - 696
VL  - 54
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/CMJ_2004_54_3_a10/
LA  - en
ID  - CMJ_2004_54_3_a10
ER  - 
%0 Journal Article
%A Saenpholphat, Varaporn
%A Zhang, Ping
%T On connected resolving decompositions in graphs
%J Czechoslovak Mathematical Journal
%D 2004
%P 681-696
%V 54
%N 3
%U http://geodesic.mathdoc.fr/item/CMJ_2004_54_3_a10/
%G en
%F CMJ_2004_54_3_a10
Saenpholphat, Varaporn; Zhang, Ping. On connected resolving decompositions in graphs. Czechoslovak Mathematical Journal, Tome 54 (2004) no. 3, pp. 681-696. http://geodesic.mathdoc.fr/item/CMJ_2004_54_3_a10/

[1] J.  Bosak: Decompositions of Graphs. Kluwer Academic, Boston, 1990. | MR | Zbl

[2] G.  Chartrand, D. Erwin, M. Raines and P.  Zhang: The decomposition dimension of graphs. Graphs and Combin. 17 (2001), 599–605. | DOI | MR

[3] G.  Chartrand and L.  Lesniak: Graphs & Digraphs, third edition. Chapman & Hall, New York, 1996. | MR

[4] H.  Enomoto and T.  Nakamigawa: On the decomposition dimension of trees. Discrete Math. 252 (2002), 219–225. | DOI | MR

[5] A.  Küngen and D. B.  West: Decomposition dimension of graphs and a union-free family of sets. Preprint.

[6] M. A.  Johnson: Structure-activity maps for visualizing the graph variables arising in drug design. J.  Biopharm. Statist. 3 (1993), 203–236. | DOI | Zbl

[7] M. A.  Johnson: Browsable structure-activity datasets. Preprint.

[8] F.  Harary and R. A.  Melter: On the metric dimension of a graph. Ars Combin. 2 (1976), 191–195. | MR

[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.

[10] B. L.  Hulme, A. W.  Shiver and P. J.  Slater: Computing minimum cost fire protection. SAND 82-0809, Sandia National Laboratories, Albuquerque, 1982.

[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

[12] P. J. Slater: Leaves of trees. Congr. Numer. 14 (1975), 549–559. | MR | Zbl

[13] P. J. Slater: Dominating and reference sets in graphs. J.  Math. Phys. Sci. 22 (1988), 445–455. | MR

[14] V.  Saenpholphat and P.  Zhang: Connected resolving decompositions in graphs. Math. Bohem. 128 (2003), 121–136. | MR