On the Strong Metric Dimension of Cartesian Sum Graphs

• Autorzy: Kuziak D. , Yero I. G. , Rodríguez-Velázquez J. A.

Identyfikatory

DOI

10.3233/FI-2015-1263

• Języki publikacji: EN

Abstrakty

EN

A vertex w of a connected graph 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 metric generator for G if every pair of vertices of G is strongly resolved by some vertex of S. The smallest cardinality of a strong metric generator for G is called the strong metric dimension of G. In this paper we obtain several tight bounds or closed formulae for the strong metric dimension of the Cartesian sum of graphs in terms of the strong metric dimension, clique number or twins-free clique number of its factor graphs.

Słowa kluczowe

EN

strong metric dimension; strong metric basis; strong metric generator; Cartesian sum graphs

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 141, nr 1
• Strony: 57--69
• Opis fizyczny: Bibliogr. 19 poz.

Twórcy

autor

Kuziak D.

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

autor

Yero I. G.

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

autor

Rodríguez-Velázquez J. A.

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

Bibliografia

• [1] Čižek, N., Klavžar, S.: On the chromatic number of the lexicographic product and the Cartesian sum of graphs, Discrete Mathematics, 134(1-3), 1994, 17–24.
• [2] Hammack, R., Imrich, W., Klavžar, S.: Handbook of product graphs, Discrete Mathematics and its Applications, 2nd ed., CRC Press, 2011.
• [3] Harary, F., Melter, R. A.: On the metric dimension of a graph, Ars Combinatoria, 2, 1976, 191–195.
• [4] Johnson, M.: Structure-activity maps for visualizing the graph variables arising in drug design, Journal of Biopharmaceutical Statistics, 3(2), 1993, 203–236.
• [5] Johnson, M.: Browsable structure-activity datasets, in: R. Carb´o-Dorca, P. Mezey (eds.), Advances in Molecular Similarity, chap. 8, JAI Press Inc, Stamford, Connecticut, 1998, pp. 153–170.
• [6] Khuller, S., Raghavachari, B., Rosenfeld, A.: Landmarks in graphs, Discrete Applied Mathematics, 70(3), 1996, 217–229.
• [7] Kuziak, D., Yero, I. G., Rodríguez-Velázquez, J. A.: On the strong metric dimension of corona product graphs and join graphs, Discrete Applied Mathematics, 161(7–8), 2013, 1022–1027.
• [8] Kuziak, D., Yero, I. G., Rodríguez-Velázquez, J. A.: Strong metric dimension of rooted product graphs, International Journal of Computer Mathematics, 2015, In press. DOI:10.1080/00207160.2015.1061656
• [9] Kuziak, D., Yero, I. G., Rodríguez-Velázquez, J. A.: Closed formulae for the strong metric dimension of lexicographic product graphs, arXiv:1402.2663v1 [math.CO].
• [10] Kuziak, D., Yero, I. G., Rodríguez-Velázquez, J. A.: On the strong metric dimension of the strong products of graphs, Open Mathematics, 13, 2015, 64–74.
• [11] Kuziak, D., Yero, I. G., Rodríguez-Velázquez, J. A.: Erratum to “On the strong metric dimension of the strong products of graphs”, Open Mathematics, 13, 2015, 209–210.
• [12] Melter, R. A., Tomescu I.:,Metric bases in digital geometry, Computer Vision, Graphics, and Image Processing, 25(1), 1984, 113–121.
• [13] Oellermann, O. R., Peters-Fransen, J.: The strong metric dimension of graphs and digraphs, Discrete Applied Mathematics, 155(3), 2007, 356–364.
• [14] Ore, O.: Theory of Graphs, Colloquium Publications, Volume 38, American Mathematical Society, 1962.
• [15] Rodríguez-Velázquez, J. A., Yero, I. G., Kuziak, D., Oellermann, O. R.: On the strong metric dimension of Cartesian and direct products of graphs, Discrete Mathematics, 335, 2014, 8–19.
• [16] Scheinerman, E. R., Ullman, D. H.: Fractional Graph Theory, Series in DiscreteMathematics and Optimization, Wiley-Interscience, 1997.
• [17] Sebö, A., Tannier, E.: On metric generators of graphs, Mathematics of Operations Research, 29(2), 2004, 383–393.
• [18] Shannon, C. E.: The zero error capacity of a noisy channel, IRE Transactions on Information Theory, 2(3), 1956, 8–19.
• [19] Slater, P. J.: Leaves of trees, Congressus Numerantium, 14, 1975, 549–559.