PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo
2015 | 13 | 1 |
Tytuł artykułu

On the strong metric dimension of the strong products of graphs

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Czasopismo
Rocznik
Tom
13
Numer
1
Opis fizyczny
Daty
wydano
2015-01-01
otrzymano
2013-08-28
zaakceptowano
2014-07-11
online
2014-10-09
Twórcy
  • Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili,
    Av. Països Catalans 26, 43007 Tarragona, Spain, dorota.kuziak@urv.cat
  • Departamento de Matemáticas, Escuela Politécnica Superior de Algeciras, Universidad de Cádiz, Av. Ramón Puyol s/n,
    11202 Algeciras, Spain, ismael.gonzalez@uca.es
  • Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili,
    Av. Països Catalans 26, 43007 Tarragona, Spain, juanalberto.rodriguez@urv.cat
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 Jornadasde 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 Cartesianproduct 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. DiscreteMath. 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 ofHamming 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 lexicographicproduct 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 ClaudeBerge, 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]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_1515_math-2015-0007
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.