| Title:
|
The local metric dimension of a graph (English) |
| Author:
|
Okamoto, Futaba |
| Author:
|
Phinezy, Bryan |
| Author:
|
Zhang, Ping |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
135 |
| Issue:
|
3 |
| Year:
|
2010 |
| Pages:
|
239-255 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
distance |
| Keyword:
|
local metric set |
| Keyword:
|
local metric dimension |
| MSC:
|
05C12 |
| idZBL:
|
Zbl 1224.05152 |
| idMR:
|
MR2683637 |
| DOI:
|
10.21136/MB.2010.140702 |
| . |
| Date available:
|
2010-07-20T18:42:44Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/140702 |
| . |
| Reference:
|
[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. Zbl 1177.05035, MR 2478212 |
| Reference:
|
[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. MR 2299707, 10.1137/S0895480102414107 |
| Reference:
|
[3] Burris, A. C., Schelp, R. H.: Vertex-distinguishing proper edge colorings.J. Graph Theory. 26 (1997), 73-82. Zbl 0886.05068, MR 1469354, 10.1002/(SICI)1097-0118(199710)26:2<73::AID-JGT2>3.0.CO;2-C |
| Reference:
|
[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. Zbl 1139.05314, MR 2318676, 10.1137/050641867 |
| Reference:
|
[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. Zbl 0958.05042, MR 1780464, 10.1016/S0166-218X(00)00198-0 |
| Reference:
|
[6] Chartrand, G., Lesniak, L., Zhang, P.: Graphs & Digraphs: Fifth Edition.Chapman & Hall/CRC, Boca Raton, FL (2010). MR 2766107 |
| Reference:
|
[7] Chartrand, G., Lesniak, L., VanderJagt, D. W., Zhang, P.: Recognizable colorings of graphs.Discuss. Math. Graph Theory. 28 (2008), 35-57. Zbl 1235.05049, MR 2438039, 10.7151/dmgt.1390 |
| Reference:
|
[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. Zbl 1193.05073, MR 2642800, 10.7151/dmgt.1463 |
| Reference:
|
[9] Chartrand, G., Okamoto, F., Salehi, E., Zhang, P.: The multiset chromatic number of a graph.Math. Bohem. 134 (2009), 191-209. Zbl 1212.05071, MR 2535147 |
| Reference:
|
[10] Chartrand, G., Okamoto, F., Zhang, P.: The metric chromatic number of a graph.Australas. J. Combin. 44 (2009), 273-286. Zbl 1181.05038, MR 2527016 |
| Reference:
|
[11] Chartrand, G., Okamoto, F., Zhang, P.: Neighbor-distinguishing vertex colorings of graphs.J. Combin. Math. Combin. Comput (to appear). MR 2675903 |
| Reference:
|
[12] Chartrand, G., Zhang, P.: Chromatic Graph Theory.Chapman & Hall/CRC Press, Boca Raton, FL (2009). Zbl 1169.05001, MR 2450569 |
| Reference:
|
[13] Harary, F., Melter, R. A.: On the metric dimension of a graph.Ars Combin. 2 (1976), 191-195. Zbl 0349.05118, MR 0457289 |
| Reference:
|
[14] Harary, F., Plantholt, M.: The point-distinguishing chromatic index.Graphs and Applications. Wiley, New York (1985), 147-162. Zbl 0562.05023, MR 0778404 |
| Reference:
|
[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. |
| Reference:
|
[16] Karoński, M., Łuczak, T., Thomason, A.: Edge weights and vertex colours.J. Combin. Theory Ser. B. 91 (2004), 151-157. Zbl 1042.05045, MR 2047539, 10.1016/j.jctb.2003.12.001 |
| Reference:
|
[17] Khuller, A., Raghavachari, B., Rosenfeld, A.: Landmarks in graphs.Discr. Appl. Math. 70 (1996), 217-229. Zbl 0865.68090, MR 1410574, 10.1016/0166-218X(95)00106-2 |
| Reference:
|
[18] Radcliffe, M., Zhang, P.: Irregular colorings of graphs.Bull. Inst. Combin. Appl. 49 (2007), 41-59. Zbl 1119.05047, MR 2285522 |
| Reference:
|
[19] Saenpholphat, V.: Resolvability in Graphs.Ph.D. Dissertation, Western Michigan University (2003). MR 2704307 |
| Reference:
|
[20] Slater, P. J.: Leaves of trees.Congress. Numer. 14 (1975), 549-559. Zbl 0316.05102, MR 0422062 |
| Reference:
|
[21] Slater, P. J.: Dominating and reference sets in graphs.J. Math. Phys. Sci. 22 (1988), 445-455. MR 0966610 |
| . |
