Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
distance; local metric set; local metric dimension
distance; local metric set; local metric dimension
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.
References:
[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 2478212 | Zbl 1177.05035
[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 10.1137/S0895480102414107 | MR 2299707
[3] Burris, A. C., Schelp, R. H.: Vertex-distinguishing proper edge colorings. J. Graph Theory. 26 (1997), 73-82. DOI 10.1002/(SICI)1097-0118(199710)26:2<73::AID-JGT2>3.0.CO;2-C | MR 1469354 | Zbl 0886.05068
[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 10.1137/050641867 | MR 2318676 | Zbl 1139.05314
[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 10.1016/S0166-218X(00)00198-0 | MR 1780464 | Zbl 0958.05042
[6] Chartrand, G., Lesniak, L., Zhang, P.: Graphs & Digraphs: Fifth Edition. Chapman & Hall/CRC, Boca Raton, FL (2010). MR 2766107
[7] Chartrand, G., Lesniak, L., VanderJagt, D. W., Zhang, P.: Recognizable colorings of graphs. Discuss. Math. Graph Theory. 28 (2008), 35-57. DOI 10.7151/dmgt.1390 | MR 2438039 | Zbl 1235.05049
[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 10.7151/dmgt.1463 | MR 2642800 | Zbl 1193.05073
[9] Chartrand, G., Okamoto, F., Salehi, E., Zhang, P.: The multiset chromatic number of a graph. Math. Bohem. 134 (2009), 191-209. MR 2535147 | Zbl 1212.05071
[10] Chartrand, G., Okamoto, F., Zhang, P.: The metric chromatic number of a graph. Australas. J. Combin. 44 (2009), 273-286. MR 2527016 | Zbl 1181.05038
[11] Chartrand, G., Okamoto, F., Zhang, P.: Neighbor-distinguishing vertex colorings of graphs. J. Combin. Math. Combin. Comput (to appear). MR 2675903
[12] Chartrand, G., Zhang, P.: Chromatic Graph Theory. Chapman & Hall/CRC Press, Boca Raton, FL (2009). MR 2450569 | Zbl 1169.05001
[13] Harary, F., Melter, R. A.: On the metric dimension of a graph. Ars Combin. 2 (1976), 191-195. MR 0457289 | Zbl 0349.05118
[14] Harary, F., Plantholt, M.: The point-distinguishing chromatic index. Graphs and Applications. Wiley, New York (1985), 147-162. MR 0778404 | Zbl 0562.05023
[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 10.1016/j.jctb.2003.12.001 | MR 2047539 | Zbl 1042.05045
[17] Khuller, A., Raghavachari, B., Rosenfeld, A.: Landmarks in graphs. Discr. Appl. Math. 70 (1996), 217-229. DOI 10.1016/0166-218X(95)00106-2 | MR 1410574 | Zbl 0865.68090
[18] Radcliffe, M., Zhang, P.: Irregular colorings of graphs. Bull. Inst. Combin. Appl. 49 (2007), 41-59. MR 2285522 | Zbl 1119.05047
[19] Saenpholphat, V.: Resolvability in Graphs. Ph.D. Dissertation, Western Michigan University (2003). MR 2704307
[20] Slater, P. J.: Leaves of trees. Congress. Numer. 14 (1975), 549-559. MR 0422062 | Zbl 0316.05102
[21] Slater, P. J.: Dominating and reference sets in graphs. J. Math. Phys. Sci. 22 (1988), 445-455. MR 0966610
Search
Partner of
