Bounds for metric dimension and defensive $k$-alliance of graphs under deleted lexicographic product

Document Type : Research Paper

Authors

1 Sungkyunkwan University

2 Department of Applied Mathematics, Faculty of Mathematical Sciences, Ferdowsi University of Mashhad

Abstract

‎Metric dimension and defensive $k$-alliance number are two distance-based graph invariants‎ ‎which have applications in robot navigation‎, ‎quantitative analysis of secondary RNA structures‎, ‎national defense and fault-tolerant computing‎. ‎In this paper‎, ‎some bounds for metric‎ ‎dimension and defensive $k$-alliance of deleted lexicographic product of graphs are presented‎. ‎We also show that the bounds are sharp‎.

Keywords


[1] J. Caceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara and D. R. Wood, On the metric dimension
of cartesian products of graphs, SIAM J. Discrete Math. 21 (2007) 423–441.
[2] A. Estrada-Moreno, C. Garcı́a-Gómez, Y. Ramı́rez-Cruz and J. A. Rodrı́guez-Velázquez, The Simultaneous Strong
Metric Dimension of Graph Families, Bull. Malays. Math. Sci. Soc., 39 (2016) 175–192.
[3] J. Feigenbaum and A. A. Schäffer, Recognizing composite graphs is equivalent to testing graph isomorphism, SIAM
J. Comput. 15 (1986) 619–627.
[4] B. Frelih and Š. Miklavič, Edge regular graph products, Electron. J. Combin. 20 (2013) pp. 62.
[5] C. E. Go, S. R. Canoy, Jr., Domination in the corona and join of graphs, Int. Math. Forum, 6 (2011) 763–771.
[6] F. Hausdorff, Grundzüge der Mengenlehre, Leipzig, 1914.
[7] T. W. Haynes, D. Knisley, E. Seier and Y. Zou, A quantitative analysis of secondary RNA structure using domi-
nation based parameters on trees, BMC Bioinformatics, 7 (2006) Pages/record No. 108.
[8] S. Khuller, B. Raghavachari and A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math., 70 (1996) 217–229.
[9] P. Kristiansen, S. M. Hedetniemi and S. T. Hedetniemi, Alliances in graphs, J. Combin. Math. Combin. Comput.,
48 (2004) 157–177.
[10] J. Quadras and S. M. M. Albert, Domination Parameters in Coronene Torus Network, Math. Comput. Sci., 9
(2015) 169–175.
[11] J. A. Rodrı́guez-Velázquez, C. G. Gómez, G. A. Barragán-Ramı́rez, On the Local Metric Dimension of Corona
Product, Bull. Malays. Math. Sci. Soc., 39 (2016) 157–173.
[12] S. W. Saputro, R. Simanjuntak, S. Uttunggadewa, H. Assiyatun, E. T. Baskoro, A. N. M. Salman and M. Bača,
The metric dimension of the lexicographic product of graphs, Discrete Math., 313 (2013) 1045–1051.
[13] K. H. Shafique and R. D. Dutton, On satisfactory partitioning of graphs, Congr. Numer., 154 (2002) 183–194.
[14] P. J. Slater, Leaves of trees, Congr. Numer., 14 (1975) 549–559.
[15] M. Tavakoli, F. Rahbarnia nd A. R. Ashrafi, Distribution of some graph invariants over hierarchical product of
graphs, Appl. Math. Comput., 220 (2013) 405–413.
[16] I. G. Yero, D. Kuziak and A. R. Aguilar, Coloring, location and domination of corona graphs, Aequat. Math. 86
(2013) 1–21.
[17] I. G. Yero, J. A. Rodríguez-Velázquez, Boundary defensive k-alliances in graphs, Discrete Appl. Math., 158
(2010)12051211.