On the strong metric dimension of the strong products of graphs

• Autorzy: Dorota Kuziak , Ismael G. Yero , Juan A. Rodríguez-Velázquez
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Strong metric dimension; Strong metric basis; Strong resolving set; Strong product graphs

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2015
• Tom: 13
• Numer: 1

Daty

wydano

2015-01-01

otrzymano

2013-08-28

zaakceptowano

2014-07-11

online

2014-10-09

Twórcy

autor

Dorota Kuziak

• Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili,
  Av. Països Catalans 26, 43007 Tarragona, Spain

autor

Ismael G. Yero

• Departamento de Matemáticas, Escuela Politécnica Superior de Algeciras, Universidad de Cádiz, Av. Ramón Puyol s/n,
  11202 Algeciras, Spain

autor

Juan A. Rodríguez-Velázquez

• Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili,
  Av. Països Catalans 26, 43007 Tarragona, Spain

Bibliografia

• [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
• [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]
• [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] 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]
• [5] Gallai T., Uber Extreme Punkt-und Kantenmengen, Ann. Univ. Sci. Budapest Eötvös Sect. Math., 1959, 2, 133–138 (in German)
• [6] Geller D., Stahl S., The chromatic number and other functions of the lexicographic product, J. Combin. Theory Ser. B, 1975, 19, 87–95
• [7] Hales R. S., Numerical invariants and the strong product of graphs, J. Combin. Theory Ser. B, 1973, 15, 146–155
• [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
• [9] Harary F., Melter R. A., On the metric dimension of a graph, Ars Combin., 1976, 2, 191–195
• [10] Jannesari M., Omoomi B., The metric dimension of the lexicographic product of graphs, Discrete Math. 2012, 312(22), 3349–3356
• [11] Jha P. K., Slutzki G., Independence numbers of product graphs, Appl. Math. Lett., 1994, 7(4), 91–94 [Crossref]
• [12] Johnson M. A., Structure-activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Statist., 1993, 3, 203–236 [Crossref]
• [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] Khuller S., Raghavachari B., Rosenfeld A., Landmarks in graphs, Discrete Appl. Math., 1996, 70, 217–229
• [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] 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]
• [17] Melter R. A., Tomescu I., Metric bases in digital geometry, Computer Vision, Graphics, and Image Processing, 1984, 25, 113–121
• [18] Oellermann O. R., Peters-Fransen J., The strong metric dimension of graphs and digraphs, Discrete Appl. Math., 2007, 155, 356–364 [WoS]
• [19] Ore, O., Theory of graphs, Amer. Math. Soc. Colloq. Publ., 38, Amer. Math. Soc., Providence, R.I., 1962
• [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
• [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
• [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
• [23] Seb˝o A., Tannier E., On metric generators of graphs, Math. Oper. Res., 2004, 29(2), 383–393 [Crossref]
• [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] 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]

Identyfikatory

DOI

10.1515/math-2015-0007