All metric bases and fault-tolerant metric dimension for square of grid

• Autorzy: Saha Laxman , Basak Mithun , Tiwary Kalishankar

Identyfikatory

DOI

10.7494/OpMath.2022.42.1.93

• Języki publikacji: EN

Abstrakty

EN

For a simple connected graph G = (V,E) and an ordered subset W = {w1, w2, . . . , wk} of V , the code of a vertex v ∈ V , denoted by code(v), with respect to W is a k-tuple (d(v, w1), . . . , d(v, wk)), where d(v, wt) represents the distance between v and wt. The set W is called a resolving set of G if code(u) ≠ code(v) for every pair of distinct vertices u and v. A metric basis of G is a resolving set with the minimum cardinality. The metric dimension of G is the cardinality of a metric basis and is denoted by β(G). A set F ⊂ V is called fault-tolerant resolving set of G if F \ {v} is a resolving set of G for every v ∈ F. The fault-tolerant metric dimension of G is the cardinality of a minimal fault-tolerant resolving set. In this article, a complete characterization of metric bases for G2 mn has been given. In addition, we prove that the fault-tolerant metric dimension of G2 mn is 4 if m + n is even. We also show that the fault-tolerant metric dimension of G2 mn is at least 5 and at most 6 when m + n is odd.

Słowa kluczowe

EN

code; resolving set; metric dimension; fault-tolerant resolving set; fault-tolerant metric dimension

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2022
• Tom: Vol. 42, no. 1
• Strony: 93--111
• Opis fizyczny: Bibliogr. 22 poz.

Twórcy

autor

Saha Laxman

• Balurghat College, Department of Mathematics, Balurghat 733101, India

• https://orcid.org/0000-0003-1563-0841

autor

Basak Mithun

• Balurghat College, Department of Mathematics, Balurghat 733101, India

• https://orcid.org/0000-0001-7496-6682

autor

Tiwary Kalishankar

• Raiganj University, Department of Mathematics, Raiganj, 733134, India

• https://orcid.org/0000-0002-5773-2021

Bibliografia

• [1] M. Basak, L. Saha, K. Tiwary, Metric dimension of zero-divisor graph for the ring Zn, Int. J. Sci. Res. Math. Stat. Sci. 6 (2019), no. 1, 74–78.
• [2] M. Basak, L. Saha, G. Das, K. Tiwary, Fault-tolerant metric dimension of circulant graphs Cn (1, 2, 3), Theor. Comput. Sci. 817 (2020), 66–79.
• [3] Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffmann, M. Mihalak, L. Ram, Network discovery and verification, IEEE J. Sel. Areas Commun. 24 (2006), 2168–2181.
• [4] J. Cáceres, C. Hernando, M. Mora, I.M. Pelayo, M. Puertas, C. Seara, D. Wood, On the metric dimension of Cartesian products of graph, SIAM J. Discrete Math. 2 (2007), no. 21, 423–441.
• [5] G. Chartrand, L. Eroh, M. Johnson, O. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000), 99–113.
• [6] K. Chau, S. Gosselin, The metric dimension of circulant graphs and their Cartesian product, Opuscula Math. 37 (2017), no. 4, 509–534.
• [7] V. Chvátal, Mastermind, Combinatorica 3 (1983), 325–329.
• [8] L. Du Toit, T. Vetrík, On the metric dimension of circulant graphs with 2 generators, Kragujevac J. Math. 43 (2019), no. 1, 49–58.
• [9] M.R. Garey, D.S. Johnson, Computers and Intractibility: A Guide to the Theory of NP-Completeness, Freeman, San Francisco 1979.
• [10] C. Grigorious, T. Kalinowski, J. Ryan, S. Stephen, The metric dimension of the circulant graph C(n,±1, 2, 3, 4), Australas. J. Combin. 69 (2017), no. 3, 417–441.
• [11] M. Hallaway, C. Kang, E. Yi, On metric dimension of permutation graphs, J. Comb. Optim. 28 (2014), 814–826.
• [12] F. Harary, R. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976), 191–195.
• [13] M. Imran, S. Bokhary, A. Baig, On the metric dimension of rotationally-symmetric convex polytopes, J. Algebra Comb. Discrete Struct. Appl. 3 (2015), no. 2, 45–59.
• [14] M. Imran, H. Siddiqui, Computing the metric dimension of convex polytopes generated wheel related graphs, Acta Math. Hungar. 149 (2016), no. 1, 10–30.
• [15] M. Jannesari, B. Omoomi, Characterization of n-vertex graphs with metric dimension (n − 3), Math. Bohem. 139 (2014), no. 1, 1–23.
• [16] S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70 (1996), 217–229.
• [17] M.A. Maryam, A.A. Omar, H. Al-Ezeh, Metric dimension of some path related graphs, Glob. J. Pure Appl. Math. 13 (2017), no. 2, 149–157.
• [18] R.A. Melter, I. Tomescu, Metric bases in digital geometry, Comput. Gr. Image Process. 25 (1984), 113–121.
• [19] L. Saha, Fault-tolerant metric dimension of cube of paths, J. Phys. Conf. Ser. 1714 (2021), no. 1, 012–019.
• [20] L. Saha, M. Basak, K. Tiwary, Metric dimension of ideal-intersection graph of the ring Zn, AKCE Int. J. Graphs Comb. 18 (2021), no. 2, 101–105.
• [21] P. Slater, Leaves of trees, Proc. 6th Southeastern Conf. on Combinatorics, Graph Theory and Computing 14 (1975), 549–559.
• [22] P. Slater, Dominating and reference sets in graphs, J. Math. Phys. 22 (1988), 445–455.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).