Characterization of n -vertex graphs with metric dimension n - 3

Mohsen Jannesari; Behnaz Omoomi

Mathematica Bohemica (2014)

  • Volume: 139, Issue: 1, page 1-23
  • ISSN: 0862-7959

Abstract

top
For an ordered set W = { w 1 , w 2 , ... , 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 ) , ... , 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 .

How to cite

top

Jannesari, Mohsen, and Omoomi, Behnaz. "Characterization of $n$-vertex graphs with metric dimension $n-3$." Mathematica Bohemica 139.1 (2014): 1-23. <http://eudml.org/doc/261079>.

@article{Jannesari2014,
abstract = {For an ordered set $W=\lbrace w_1,w_2,\ldots ,w_k\rbrace $ 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$.},
author = {Jannesari, Mohsen, Omoomi, Behnaz},
journal = {Mathematica Bohemica},
keywords = {resolving set; basis; metric dimension; resolving set; basis; metric dimension},
language = {eng},
number = {1},
pages = {1-23},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Characterization of $n$-vertex graphs with metric dimension $n-3$},
url = {http://eudml.org/doc/261079},
volume = {139},
year = {2014},
}

TY - JOUR
AU - Jannesari, Mohsen
AU - Omoomi, Behnaz
TI - Characterization of $n$-vertex graphs with metric dimension $n-3$
JO - Mathematica Bohemica
PY - 2014
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 139
IS - 1
SP - 1
EP - 23
AB - For an ordered set $W=\lbrace w_1,w_2,\ldots ,w_k\rbrace $ 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$.
LA - eng
KW - resolving set; basis; metric dimension; resolving set; basis; metric dimension
UR - http://eudml.org/doc/261079
ER -

References

top
  1. Cáceres, J., Hernando, C., Mora, M., Pelayo, I. M., Puertas, M. L., Seara, C., Wood, D. R., 10.1137/050641867, SIAM J. Discrete Math. (electronic) 21 (2007), 423-441. (2007) Zbl1139.05314MR2318676DOI10.1137/050641867
  2. Chartrand, G., Eroh, L., Johnson, M. A., Ollermann, O. R., 10.1016/S0166-218X(00)00198-0, Discrete Appl. Math. 105 (2000), 99-113. (2000) MR1780464DOI10.1016/S0166-218X(00)00198-0
  3. Chartrand, G., Poisson, C., Zhang, P., 10.1016/S0898-1221(00)00126-7, Comput. Math. Appl. 39 (2000), 19-28. (2000) Zbl0953.05021MR1763834DOI10.1016/S0898-1221(00)00126-7
  4. Chartrand, G., Zhang, P., The theory and applications of resolvability in graphs (A survey), Congr. Numerantium 160 (2003), 47-68. (2003) Zbl1039.05029MR2049102
  5. Harary, F., Melter, R. A., On the metric dimension of a graph, Ars Comb. 2 (1976), 191-195. (1976) Zbl0349.05118MR0457289
  6. Hernando, C., Mora, M., Pelayo, I. M., Seara, C., Cáceres, J., Puertas, M. L., 10.1016/j.endm.2005.06.023, 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. (2005) Zbl1182.05050MR2521989DOI10.1016/j.endm.2005.06.023
  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. (2010) Zbl1219.05051MR2595490
  8. Khuller, S., Raghavachari, B., Rosenfeld, A., 10.1016/0166-218X(95)00106-2, Discrete Appl. Math. 70 (1996), 217-229. (1996) Zbl0865.68090MR1410574DOI10.1016/0166-218X(95)00106-2
  9. Sebö, A., Tannier, E., 10.1287/moor.1030.0070, Math. Oper. Res. 29 (2004), 383-393. (2004) Zbl1082.05032MR2065985DOI10.1287/moor.1030.0070
  10. Slater, P. J., Leaves of trees, Proc. 6th Southeast. Conf. Comb., Graph Theor., Comput Florida, Boca Raton (1975), 549-559. (1975) Zbl0316.05102MR0422062
  11. Sudhakara, G., Kumar, A. R. Hemanth, Graphs with metric dimension two---a characterization, Adv. Appl. Discrete Math. 4 (2009), 169-186. (2009) MR2590304
  12. Yero, I. G., Kuziak, D., Rodríguez-Velázquez, J. A., 10.1016/j.camwa.2011.03.046, Comput. Math. Appl. 61 (2011), 2793-2798. (2011) Zbl1221.05252MR2795402DOI10.1016/j.camwa.2011.03.046

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.