Geodesic
Connected resolving decompositions in graphs
Mathematica Bohemica, Tome 128 (2003) no. 2, pp. 121-136

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
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$.
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$.
DOI : 10.21136/MB.2003.134033
Classification : 05C12
Keywords: distance; resolving decomposition; connected resolving decomposition 
Saenpholphat, Varaporn; Zhang, Ping. Connected resolving decompositions in graphs. Mathematica Bohemica, Tome 128 (2003) no. 2, pp. 121-136. doi: 10.21136/MB.2003.134033
@article{10_21136_MB_2003_134033,
     author = {Saenpholphat, Varaporn and Zhang, Ping},
     title = {Connected resolving decompositions in graphs},
     journal = {Mathematica Bohemica},
     pages = {121--136},
     year = {2003},
     volume = {128},
     number = {2},
     doi = {10.21136/MB.2003.134033},
     mrnumber = {1995567},
     zbl = {1021.05030},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2003.134033/}
}
TY  - JOUR
AU  - Saenpholphat, Varaporn
AU  - Zhang, Ping
TI  - Connected resolving decompositions in graphs
JO  - Mathematica Bohemica
PY  - 2003
SP  - 121
EP  - 136
VL  - 128
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2003.134033/
DO  - 10.21136/MB.2003.134033
LA  - en
ID  - 10_21136_MB_2003_134033
ER  - 
%0 Journal Article
%A Saenpholphat, Varaporn
%A Zhang, Ping
%T Connected resolving decompositions in graphs
%J Mathematica Bohemica
%D 2003
%P 121-136
%V 128
%N 2
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2003.134033/
%R 10.21136/MB.2003.134033
%G en
%F 10_21136_MB_2003_134033

[1] J. Bosák: Decompositions of Graphs. Kluwer Academic, Boston, 1990. | MR

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

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

[4] H. Enomoto, T. Nakamigawa: On the decomposition dimension of trees. Preprint. | MR

[5] A. Küngen, D. B. West: Decomposition dimension of graphs and 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, R. A. Melter: On the metric dimension of a graph. Ars Combin. 2 (1976), 191–195. | MR

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

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

Cité par Sources :