The local metric dimension of a graph

Futaba Okamoto; Bryan Phinezy; Ping Zhang

Mathematica Bohemica (2010)

  • Volume: 135, Issue: 3, page 239-255
  • ISSN: 0862-7959

Abstract

top
For an ordered set W = { w 1 , w 2 , ... , 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 code ( v ) = ( d ( v , w 1 ) , d ( v , w 2 ) , , d ( v , w k ) ) where d ( v , w i ) is the distance between v and w i for 1 i k . The set W is a local metric set of G if code ( u ) 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 lmd ( G ) of G . A local metric set of G of cardinality 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.

How to cite

top

Okamoto, Futaba, Phinezy, Bryan, and Zhang, Ping. "The local metric dimension of a graph." Mathematica Bohemica 135.3 (2010): 239-255. <http://eudml.org/doc/38128>.

@article{Okamoto2010,
abstract = {For an ordered set $W= \lbrace w_1,w_2,\ldots ,w_k\rbrace $ 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.},
author = {Okamoto, Futaba, Phinezy, Bryan, Zhang, Ping},
journal = {Mathematica Bohemica},
keywords = {distance; local metric set; local metric dimension; distance; local metric set; local metric dimension},
language = {eng},
number = {3},
pages = {239-255},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {The local metric dimension of a graph},
url = {http://eudml.org/doc/38128},
volume = {135},
year = {2010},
}

TY - JOUR
AU - Okamoto, Futaba
AU - Phinezy, Bryan
AU - Zhang, Ping
TI - The local metric dimension of a graph
JO - Mathematica Bohemica
PY - 2010
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 135
IS - 3
SP - 239
EP - 255
AB - For an ordered set $W= \lbrace w_1,w_2,\ldots ,w_k\rbrace $ 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.
LA - eng
KW - distance; local metric set; local metric dimension; distance; local metric set; local metric dimension
UR - http://eudml.org/doc/38128
ER -

References

top
  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. (2009) Zbl1177.05035MR2478212
  2. Balister, P. N., Győri, E., Lehel, J., Schelp, R. H., 10.1137/S0895480102414107, SIAM J. Discrete Math. 21 (2007), 237-250. (2007) MR2299707DOI10.1137/S0895480102414107
  3. Burris, A. C., Schelp, R. H., 10.1002/(SICI)1097-0118(199710)26:2<73::AID-JGT2>3.0.CO;2-C, J. Graph Theory. 26 (1997), 73-82. (1997) Zbl0886.05068MR1469354DOI10.1002/(SICI)1097-0118(199710)26:2<73::AID-JGT2>3.0.CO;2-C
  4. Caceres, J., Hernando, C., Mora, M., Pelayo, I. M., Puertas, M. L., Seara, C., Wood, D. R., 10.1137/050641867, SIAM J. Discr. Math. 21 (2007), 423-441. (2007) Zbl1139.05314MR2318676DOI10.1137/050641867
  5. Chartrand, G., Eroh, L., Johnson, M. A., Oellermann, O. R., 10.1016/S0166-218X(00)00198-0, Discrete Appl. Math. 105 (2000), 99-113. (2000) Zbl0958.05042MR1780464DOI10.1016/S0166-218X(00)00198-0
  6. Chartrand, G., Lesniak, L., Zhang, P., Graphs & Digraphs: Fifth Edition, Chapman & Hall/CRC, Boca Raton, FL (2010). (2010) MR2766107
  7. Chartrand, G., Lesniak, L., VanderJagt, D. W., Zhang, P., 10.7151/dmgt.1390, Discuss. Math. Graph Theory. 28 (2008), 35-57. (2008) Zbl1235.05049MR2438039DOI10.7151/dmgt.1390
  8. Chartrand, G., Okamoto, F., Rasmussen, C. W., Zhang, P., 10.7151/dmgt.1463, Discuss. Math. Graph Theory. 29 (2009), 545-561. (2009) Zbl1193.05073MR2642800DOI10.7151/dmgt.1463
  9. Chartrand, G., Okamoto, F., Salehi, E., Zhang, P., The multiset chromatic number of a graph, Math. Bohem. 134 (2009), 191-209. (2009) Zbl1212.05071MR2535147
  10. Chartrand, G., Okamoto, F., Zhang, P., The metric chromatic number of a graph, Australas. J. Combin. 44 (2009), 273-286. (2009) Zbl1181.05038MR2527016
  11. Chartrand, G., Okamoto, F., Zhang, P., Neighbor-distinguishing vertex colorings of graphs, J. Combin. Math. Combin. Comput (to appear). MR2675903
  12. Chartrand, G., Zhang, P., Chromatic Graph Theory, Chapman & Hall/CRC Press, Boca Raton, FL (2009). (2009) Zbl1169.05001MR2450569
  13. Harary, F., Melter, R. A., On the metric dimension of a graph, Ars Combin. 2 (1976), 191-195. (1976) Zbl0349.05118MR0457289
  14. Harary, F., Plantholt, M., The point-distinguishing chromatic index, Graphs and Applications. Wiley, New York (1985), 147-162. (1985) Zbl0562.05023MR0778404
  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. (2007) 
  16. Karoński, M., Łuczak, T., Thomason, A., 10.1016/j.jctb.2003.12.001, J. Combin. Theory Ser. B. 91 (2004), 151-157. (2004) Zbl1042.05045MR2047539DOI10.1016/j.jctb.2003.12.001
  17. Khuller, A., Raghavachari, B., Rosenfeld, A., 10.1016/0166-218X(95)00106-2, Discr. Appl. Math. 70 (1996), 217-229. (1996) Zbl0865.68090MR1410574DOI10.1016/0166-218X(95)00106-2
  18. Radcliffe, M., Zhang, P., Irregular colorings of graphs, Bull. Inst. Combin. Appl. 49 (2007), 41-59. (2007) Zbl1119.05047MR2285522
  19. Saenpholphat, V., Resolvability in Graphs, Ph.D. Dissertation, Western Michigan University (2003). (2003) MR2704307
  20. Slater, P. J., Leaves of trees, Congress. Numer. 14 (1975), 549-559. (1975) Zbl0316.05102MR0422062
  21. Slater, P. J., Dominating and reference sets in graphs, J. Math. Phys. Sci. 22 (1988), 445-455. (1988) MR0966610

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.