On the strong metric dimension of the strong products of graphs

Dorota Kuziak; Ismael G. Yero; Juan A. Rodríguez-Velázquez

Open Mathematics (2015)

  • Volume: 13, Issue: 1, page 209-210, electronic only
  • ISSN: 2391-5455

Abstract

top
Let G be a connected graph. A vertex w ∈ V.G/ strongly resolves two vertices u,v ∈ V.G/ if there exists some shortest u-w path containing v or some shortest v-w path containing u. A set S of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of S. The smallest cardinality of a strong resolving set for G is called the strong metric dimension of G. It is well known that the problem of computing this invariant is NP-hard. In this paper we study the problem of finding exact values or sharp bounds for the strong metric dimension of strong product graphs and express these in terms of invariants of the factor graphs.

How to cite

top

Dorota Kuziak, Ismael G. Yero, and Juan A. Rodríguez-Velázquez. "On the strong metric dimension of the strong products of graphs." Open Mathematics 13.1 (2015): 209-210, electronic only. <http://eudml.org/doc/271930>.

@article{DorotaKuziak2015,
abstract = {Let G be a connected graph. A vertex w ∈ V.G/ strongly resolves two vertices u,v ∈ V.G/ if there exists some shortest u-w path containing v or some shortest v-w path containing u. A set S of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of S. The smallest cardinality of a strong resolving set for G is called the strong metric dimension of G. It is well known that the problem of computing this invariant is NP-hard. In this paper we study the problem of finding exact values or sharp bounds for the strong metric dimension of strong product graphs and express these in terms of invariants of the factor graphs.},
author = {Dorota Kuziak, Ismael G. Yero, Juan A. Rodríguez-Velázquez},
journal = {Open Mathematics},
keywords = {Strong metric dimension; Strong metric basis; Strong resolving set; Strong product graphs; strong metric dimension; strong metric basis; strong resolving set; strong product graphs},
language = {eng},
number = {1},
pages = {209-210, electronic only},
title = {On the strong metric dimension of the strong products of graphs},
url = {http://eudml.org/doc/271930},
volume = {13},
year = {2015},
}

TY - JOUR
AU - Dorota Kuziak
AU - Ismael G. Yero
AU - Juan A. Rodríguez-Velázquez
TI - On the strong metric dimension of the strong products of graphs
JO - Open Mathematics
PY - 2015
VL - 13
IS - 1
SP - 209
EP - 210, electronic only
AB - Let G be a connected graph. A vertex w ∈ V.G/ strongly resolves two vertices u,v ∈ V.G/ if there exists some shortest u-w path containing v or some shortest v-w path containing u. A set S of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of S. The smallest cardinality of a strong resolving set for G is called the strong metric dimension of G. It is well known that the problem of computing this invariant is NP-hard. In this paper we study the problem of finding exact values or sharp bounds for the strong metric dimension of strong product graphs and express these in terms of invariants of the factor graphs.
LA - eng
KW - Strong metric dimension; Strong metric basis; Strong resolving set; Strong product graphs; strong metric dimension; strong metric basis; strong resolving set; strong product graphs
UR - http://eudml.org/doc/271930
ER -

References

top
  1. [1] Cáceres J. , Hernando C., Mora M., Pelayo I. M., Puertas M. L., Boundary-type sets and product operators in graphs, In: VII Jornadas de Matemática Discreta y Algorítmica, Castro Urdiales, Cantabria, Spain, July 2010 Zbl1207.05043
  2. [2] Cáceres J., Hernando C., Mora M., Pelayo I. M., Puertas M. L., Seara C., Wood D. R., On the metric dimension of Cartesian product of graphs, SIAM J. Discrete Math., 2007, 21(2), 273–302 [WoS] Zbl1139.05314
  3. [3] Cˇ ižek N., Klavžar S., On the chromatic number of the lexicographic product and the Cartesian sum of graphs, Discrete Math., 1994, 134(1-3), 17–24 
  4. [4] Feng M., Wang K., On the metric dimension and fractional metric dimension of the hierarchical product of graphs, Appl. Anal. Discrete Math., 2013, 7, 302–313 [WoS][Crossref] Zbl06451378
  5. [5] Gallai T., Uber Extreme Punkt-und Kantenmengen, Ann. Univ. Sci. Budapest Eötvös Sect. Math., 1959, 2, 133–138 (in German) 
  6. [6] Geller D., Stahl S., The chromatic number and other functions of the lexicographic product, J. Combin. Theory Ser. B, 1975, 19, 87–95 Zbl0282.05114
  7. [7] Hales R. S., Numerical invariants and the strong product of graphs, J. Combin. Theory Ser. B, 1973, 15, 146–155 Zbl0247.05122
  8. [8] Hammack R., Imrich W., Klavžar S., Handbook of Product Graphs, Second edition. With a foreword by Peter Winkler. Discrete Math. Appl. (Boca Raton), CRC Press, Boca Raton, FL, 2011 Zbl1283.05001
  9. [9] Harary F., Melter R. A., On the metric dimension of a graph, Ars Combin., 1976, 2, 191–195 Zbl0349.05118
  10. [10] Jannesari M., Omoomi B., The metric dimension of the lexicographic product of graphs, Discrete Math. 2012, 312(22), 3349–3356 Zbl1252.05187
  11. [11] Jha P. K., Slutzki G., Independence numbers of product graphs, Appl. Math. Lett., 1994, 7(4), 91–94 [Crossref] Zbl0811.05033
  12. [12] Johnson M. A., Structure-activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Statist., 1993, 3, 203–236 [Crossref] Zbl0800.92106
  13. [13] Johnson M. A., Browsable structure-activity datasets, In: Advances in Molecular Similarity, R. Carbó–Dorca and P. Mezey, eds., JAI Press Connecticut, 1998, 153–170 
  14. [14] Khuller S., Raghavachari B., Rosenfeld A., Landmarks in graphs, Discrete Appl. Math., 1996, 70, 217–229 Zbl0865.68090
  15. [15] Kratica J., Kovacˇevic´-Vujcˇic´ V., Cˇ angalovic´ M., Stojanovic´ M., Minimal doubly resolving sets and the strong metric dimension of Hamming graphs, Appl. Anal. Discrete Math., 2012, 6, 63–71 [Crossref][WoS] 
  16. [16] Kuziak D., Yero I. G., Rodríguez-Velázquez J. A., On the strong metric dimension of corona product graphs and join graphs, Discrete Appl. Math., 2013, 161(7-8), 1022–1027 [WoS] Zbl1262.05133
  17. [17] Melter R. A., Tomescu I., Metric bases in digital geometry, Computer Vision, Graphics, and Image Processing, 1984, 25, 113–121 Zbl0591.51023
  18. [18] Oellermann O. R., Peters-Fransen J., The strong metric dimension of graphs and digraphs, Discrete Appl. Math., 2007, 155, 356–364 [WoS] Zbl1111.05030
  19. [19] Ore, O., Theory of graphs, Amer. Math. Soc. Colloq. Publ., 38, Amer. Math. Soc., Providence, R.I., 1962 Zbl0105.35401
  20. [20] Rodríguez-Velázquez J. A., Kuziak D., Yero I. G., Sigarreta J. M., The metric dimension of strong product graphs, Carpathian J. Math. (in press), preprint available at http://arxiv.org/abs/1305.0363 Zbl06582104
  21. [21] Saputro S., Simanjuntak R., Uttunggadewa S., Assiyatun H., Baskoro E., Salman A., Baˇca M., The metric dimension of the lexicographic product of graphs, Discrete Math., 2013, 313(9), 1045–1051 Zbl1263.05085
  22. [22] Scheinerman E., Ullman D., Fractional Graph Theory. A rational approach to the theory of graphs. With a foreword by Claude Berge, Wiley-Intersci. Ser. Discrete Math. Optim., A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1997 Zbl0891.05003
  23. [23] Seb˝o A., Tannier E., On metric generators of graphs, Math. Oper. Res., 2004, 29(2), 383–393 [Crossref] Zbl1082.05032
  24. [24] Slater P. J., Leaves of trees, In: Proceeding of the 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing. Congr. Numer., 1975, 14, 549–559 
  25. [25] Yero I. G., Kuziak D., Rodríguez-Velázquez J. A., On the metric dimension of corona product graphs, Comput. Math. Appl., 2011, 61(9), 2793–2798[WoS] Zbl1221.05252

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.