| Title:
|
Characterization of $n$-vertex graphs with metric dimension $n-3$ (English) |
| Author:
|
Jannesari, Mohsen |
| Author:
|
Omoomi, Behnaz |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
139 |
| Issue:
|
1 |
| Year:
|
2014 |
| Pages:
|
1-23 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
For an ordered set $W=\{w_1,w_2,\ldots ,w_k\}$ of vertices and a vertex $v$ in a connected graph $G$, the ordered $k$-vector $r(v|W):=(d(v,w_1),d(v,w_2),\ldots ,d(v,w_k))$ is called the metric representation of $v$ with respect to $W$, where $d(x,y)$ is the distance between vertices $x$ and $y$. A set $W$ is called a resolving set for $G$ if distinct vertices of $G$ have distinct representations with respect to $W$. The minimum cardinality of a resolving set for $G$ is its metric dimension. In this paper, we characterize all graphs of order $n$ with metric dimension $n-3$. (English) |
| Keyword:
|
resolving set |
| Keyword:
|
basis |
| Keyword:
|
metric dimension |
| MSC:
|
05C12 |
| idZBL:
|
Zbl 06362240 |
| idMR:
|
MR3231427 |
| DOI:
|
10.21136/MB.2014.143632 |
| . |
| Date available:
|
2014-03-20T08:25:19Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143632 |
| . |
| Reference:
|
[1] Cáceres, 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. Discrete Math. (electronic) 21 (2007), 423-441. Zbl 1139.05314, MR 2318676, 10.1137/050641867 |
| Reference:
|
[2] Chartrand, G., Eroh, L., Johnson, M. A., Ollermann, O. R.: Resolvability in graphs and the metric dimension of a graph.Discrete Appl. Math. 105 (2000), 99-113. MR 1780464, 10.1016/S0166-218X(00)00198-0 |
| Reference:
|
[3] Chartrand, G., Poisson, C., Zhang, P.: Resolvability and the upper dimension of graphs.Comput. Math. Appl. 39 (2000), 19-28. Zbl 0953.05021, MR 1763834, 10.1016/S0898-1221(00)00126-7 |
| Reference:
|
[4] Chartrand, G., Zhang, P.: The theory and applications of resolvability in graphs (A survey).Congr. Numerantium 160 (2003), 47-68. Zbl 1039.05029, MR 2049102 |
| Reference:
|
[5] Harary, F., Melter, R. A.: On the metric dimension of a graph.Ars Comb. 2 (1976), 191-195. Zbl 0349.05118, MR 0457289 |
| Reference:
|
[6] Hernando, C., Mora, M., Pelayo, I. M., Seara, C., Cáceres, J., Puertas, M. L.: On the metric dimension of some families of graphs.Raspaud, André et al. 7th International Colloquium on Graph Theory, Hyeres, France, September 12-16, 2005 Elsevier, Amsterdam, Electronic Notes in Discrete Mathematics 22 (2005), 129-133. Zbl 1182.05050, MR 2521989, 10.1016/j.endm.2005.06.023 |
| Reference:
|
[7] Hernando, C., Mora, M., Pelayo, I. M., Seara, C., Wood, D. R.: Extremal graph theory for metric dimension and diameter.Electron. J. Comb. 17 (2010), Research paper R30, 28 pages. Zbl 1219.05051, MR 2595490 |
| Reference:
|
[8] Khuller, S., Raghavachari, B., Rosenfeld, A.: Landmarks in graphs.Discrete Appl. Math. 70 (1996), 217-229. Zbl 0865.68090, MR 1410574, 10.1016/0166-218X(95)00106-2 |
| Reference:
|
[9] Sebö, A., Tannier, E.: On metric generators of graphs.Math. Oper. Res. 29 (2004), 383-393. Zbl 1082.05032, MR 2065985, 10.1287/moor.1030.0070 |
| Reference:
|
[10] Slater, P. J.: Leaves of trees.Proc. 6th Southeast. Conf. Comb., Graph Theor., Comput Florida, Boca Raton (1975), 549-559. Zbl 0316.05102, MR 0422062 |
| Reference:
|
[11] Sudhakara, G., Kumar, A. R. Hemanth: Graphs with metric dimension two---a characterization.Adv. Appl. Discrete Math. 4 (2009), 169-186. MR 2590304 |
| Reference:
|
[12] Yero, I. G., Kuziak, D., Rodríguez-Velázquez, J. A.: On the metric dimension of corona product graphs.Comput. Math. Appl. 61 (2011), 2793-2798. Zbl 1221.05252, MR 2795402, 10.1016/j.camwa.2011.03.046 |
| . |
