Geodesic
The local metric dimension of a graph
Mathematica Bohemica, Tome 135 (2010) no. 3, pp. 239-255

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

MR Zbl
For an ordered set $W= \{w_1,w_2,\ldots ,w_k\}$ of $k$ distinct vertices in a nontrivial connected graph $G$, the metric code of a vertex $v$ of $G$ with respect to $W$ is the $k$-vector \[ \mathop {\rm code}(v)= ( d(v,w_1),d(v,w_2),\cdots ,d(v,w_k) ) \] where $d(v,w_i)$ is the distance between $v$ and $w_i$ for $1\le i\le k$. The set $W$ is a local metric set of $G$ if $\mathop {\rm code}(u)\ne \mathop {\rm code}(v)$ for every pair $u,v$ of adjacent vertices of $G$. The minimum positive integer $k$ for which $G$ has a local metric $k$-set is the local metric dimension $\mathop {\rm lmd}(G)$ of $G$. A local metric set of $G$ of cardinality $\mathop {\rm lmd}(G)$ is a local metric basis of $G$. We characterize all nontrivial connected graphs of order $n$ having local metric dimension $1$, $n-2$, or $n-1$ and establish sharp bounds for the local metric dimension of a graph in terms of well-known graphical parameters. Several realization results are presented along with other results on the number of local metric bases of a connected graph.
For an ordered set $W= \{w_1,w_2,\ldots ,w_k\}$ of $k$ distinct vertices in a nontrivial connected graph $G$, the metric code of a vertex $v$ of $G$ with respect to $W$ is the $k$-vector \[ \mathop {\rm code}(v)= ( d(v,w_1),d(v,w_2),\cdots ,d(v,w_k) ) \] where $d(v,w_i)$ is the distance between $v$ and $w_i$ for $1\le i\le k$. The set $W$ is a local metric set of $G$ if $\mathop {\rm code}(u)\ne \mathop {\rm code}(v)$ for every pair $u,v$ of adjacent vertices of $G$. The minimum positive integer $k$ for which $G$ has a local metric $k$-set is the local metric dimension $\mathop {\rm lmd}(G)$ of $G$. A local metric set of $G$ of cardinality $\mathop {\rm lmd}(G)$ is a local metric basis of $G$. We characterize all nontrivial connected graphs of order $n$ having local metric dimension $1$, $n-2$, or $n-1$ and establish sharp bounds for the local metric dimension of a graph in terms of well-known graphical parameters. Several realization results are presented along with other results on the number of local metric bases of a connected graph.
DOI : 10.21136/MB.2010.140702
Classification : 05C12
Keywords: distance; local metric set; local metric dimension 
Okamoto, Futaba; Phinezy, Bryan; Zhang, Ping. The local metric dimension of a graph. Mathematica Bohemica, Tome 135 (2010) no. 3, pp. 239-255. doi: 10.21136/MB.2010.140702
@article{10_21136_MB_2010_140702,
     author = {Okamoto, Futaba and Phinezy, Bryan and Zhang, Ping},
     title = {The local metric dimension of a graph},
     journal = {Mathematica Bohemica},
     pages = {239--255},
     year = {2010},
     volume = {135},
     number = {3},
     doi = {10.21136/MB.2010.140702},
     mrnumber = {2683637},
     zbl = {1224.05152},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2010.140702/}
}
TY  - JOUR
AU  - Okamoto, Futaba
AU  - Phinezy, Bryan
AU  - Zhang, Ping
TI  - The local metric dimension of a graph
JO  - Mathematica Bohemica
PY  - 2010
SP  - 239
EP  - 255
VL  - 135
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2010.140702/
DO  - 10.21136/MB.2010.140702
LA  - en
ID  - 10_21136_MB_2010_140702
ER  - 
%0 Journal Article
%A Okamoto, Futaba
%A Phinezy, Bryan
%A Zhang, Ping
%T The local metric dimension of a graph
%J Mathematica Bohemica
%D 2010
%P 239-255
%V 135
%N 3
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2010.140702/
%R 10.21136/MB.2010.140702
%G en
%F 10_21136_MB_2010_140702

[1] Anderson, M., Barrientos, C., Brigham, R. C., Carrington, J. R., Kronman, M., Vitray, R. P., Yellen, J.: Irregular colorings of some graph classes. Bull. Inst. Combin. Appl. 55 (2009), 105-119. | MR | Zbl

[2] Balister, P. N., Győri, E., Lehel, J., Schelp, R. H.: Adjacent vertex distinguishing edge-colorings. SIAM J. Discrete Math. 21 (2007), 237-250. | DOI | MR

[3] Burris, A. C., Schelp, R. H.: Vertex-distinguishing proper edge colorings. J. Graph Theory. 26 (1997), 73-82. | DOI | MR | Zbl

[4] Caceres, J., Hernando, C., Mora, M., Pelayo, I. M., Puertas, M. L., Seara, C., Wood, D. R.: On the metric dimension of Cartesian products of graphs. SIAM J. Discr. Math. 21 (2007), 423-441. | DOI | MR | Zbl

[5] Chartrand, G., Eroh, L., Johnson, M. A., Oellermann, O. R.: Resolvability in graphs and the metric dimension of a graph. Discrete Appl. Math. 105 (2000), 99-113. | DOI | MR | Zbl

[6] Chartrand, G., Lesniak, L., Zhang, P.: Graphs & Digraphs: Fifth Edition. Chapman & Hall/CRC, Boca Raton, FL (2010). | MR

[7] Chartrand, G., Lesniak, L., VanderJagt, D. W., Zhang, P.: Recognizable colorings of graphs. Discuss. Math. Graph Theory. 28 (2008), 35-57. | DOI | MR | Zbl

[8] Chartrand, G., Okamoto, F., Rasmussen, C. W., Zhang, P.: The set chromatic number of a graph. Discuss. Math. Graph Theory. 29 (2009), 545-561. | DOI | MR | Zbl

[9] Chartrand, G., Okamoto, F., Salehi, E., Zhang, P.: The multiset chromatic number of a graph. Math. Bohem. 134 (2009), 191-209. | MR | Zbl

[10] Chartrand, G., Okamoto, F., Zhang, P.: The metric chromatic number of a graph. Australas. J. Combin. 44 (2009), 273-286. | MR | Zbl

[11] Chartrand, G., Okamoto, F., Zhang, P.: Neighbor-distinguishing vertex colorings of graphs. J. Combin. Math. Combin. Comput (to appear). | MR

[12] Chartrand, G., Zhang, P.: Chromatic Graph Theory. Chapman & Hall/CRC Press, Boca Raton, FL (2009). | MR | Zbl

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

[14] Harary, F., Plantholt, M.: The point-distinguishing chromatic index. Graphs and Applications. Wiley, New York (1985), 147-162. | MR | Zbl

[15] Hernando, C., Mora, M., Pelayo, I. M., Seara, C., Wood, D. R.: Extremal graph theory for the metric dimension and diameter. Electronic Notes in Discrete Mathematics 29 (2007), 339-343.

[16] Karoński, M., Łuczak, T., Thomason, A.: Edge weights and vertex colours. J. Combin. Theory Ser. B. 91 (2004), 151-157. | DOI | MR | Zbl

[17] Khuller, A., Raghavachari, B., Rosenfeld, A.: Landmarks in graphs. Discr. Appl. Math. 70 (1996), 217-229. | DOI | MR | Zbl

[18] Radcliffe, M., Zhang, P.: Irregular colorings of graphs. Bull. Inst. Combin. Appl. 49 (2007), 41-59. | MR | Zbl

[19] Saenpholphat, V.: Resolvability in Graphs. Ph.D. Dissertation, Western Michigan University (2003). | MR

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

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

Cité par Sources :