On metric dimension of cube of trees

Articles in Press

Document Type : Original paper

Authors

1 Department of Mathematics, C.V. Raman Global University, Bhubaneswar 752054, India

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

3 Department of Mathematics, Presidency University, Kolkata 700073, India

Abstract

Let G=(V,E) be a connected graph and dG(u,v) be the shortest distance between the vertices u and v in G. A set S={s1,s2,…,sn}⊂V(G) is said to be a {\em resolving set} if for all distinct vertices u,v of G, there exists an element s∈S such that dG(s,u)≠dG(s,v). The minimum cardinality of a resolving set for a graph G is called the metric dimension of G, and it is denoted by β(G). A resolving set having β(G) number of vertices is named as metric basis of G. The metric dimension problem is to find a metric basis in a graph G, and it has several real-life applications in network theory, telecommunication, image processing, pattern recognition, and many other fields. In this article, we consider cube of trees T3=(V,E), where any two vertices u,v are adjacent if and only if the distance between them is less than or equal to three in T. We establish the necessary and sufficient conditions for a vertex subset of V to become a resolving set for T3. This helps to determine the tight bounds (upper and lower) on the metric dimension of T3. Then, for certain well-known cube of trees, such as caterpillars, lobsters, spiders, and d-regular trees, we establish the boundaries for the metric dimension. Also, for every positive integer, we provide a construction showing the existence of a cube of a tree satisfying its metric dimension as the given integer. Further, we characterize some restricted families of cube of trees satisfying β(T3)=β(T).

Keywords

Main Subjects

References

[1] R. Adar and L. Epstein, The weighted 2-metric dimension of trees in the non-landmarks model, Discrete Optim. 17 (2015), 123–135.  https://doi.org/10.1016/j.disopt.2015.06.001
[2] M.M. AlHoli, O.A. AbuGhneim, and H.A. Ezeh, Metric dimension of some path related graphs, Global J. Pure Appl. Math. 13 (2017), no. 2, 149–157.
[3] M. Ali, M.T. Rahim, and G. Ali, On path related graphs with constant metric dimension, Util. Math. 88 (2012), 203–209.
[4] R.F. Bailey and P.J. Cameron, Base size, metric dimension and other invariants of groups and graphs, Bull. Lond. Math. Soc. 43 (2011), no. 2, 209–242.  https://doi.org/10.1112/blms/bdq096
[5] R.F. Bailey and I. González Yero, Error-correcting codes from k-resolving sets, Discuss. Math. Graph Theory 39 (2019), no. 2, 341–355. https://doi.org/10.7151/dmgt.2087
[6] Z. Bartha, J. Komjáthy, and J. Raes, Sharp bound on the truncated metric dimension of trees, Discrete Math. 346 (2023), no. 8, Article ID: 113410.  https://doi.org/10.1016/j.disc.2023.113410
[7] P. Buczkowski, G. Chartrand, C. Poisson, and P. Zhang, On k-dimensional graphs and their bases, Period. Math. Hungar. 46 (2003), no. 1, 9–15.  https://doi.org/10.1023/a:1025745406160
[8] G. Chartrand, L. Eroh, M.A. Johnson, and O.R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000), no. 1-3, 99–113.  https://doi.org/10.1016/S0166-218X(00)00198-0
[9] E. Galby, L. Khazaliya, F. Mc Inerney, R. Sharma, and P. Tale, Metric dimension  parameterized by feedback vertex set and other structural parameters, SIAM J.  Discrete Math. 37 (2023), no. 4, 2241–2264.  https://doi.org/10.1137/22M1510911
[10] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, wh freeman New York, 2002. 
[11] A. Hakanen, V. Junnila, T. Laihonen, and I.G. Yero, On vertices contained in all or in no metric basis, Discrete Appl. Math. 319 (2022), 407–423.  https://doi.org/10.1016/j.dam.2021.12.004
[12] F. Harary and R.A. Melter, On the metric dimension of a graph, Ars. Combin. 2 (1976), 191–195.
[13] I. Javaid, M.T. Rahim, and K. Ali, Families of regular graphs with constant metric  dimension, Util. Math. 75 (2008), no. 1, 21–33.
[14] S. Khuller, B. Raghavachari, and A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70 (1996), no. 3, 217–229. https://doi.org/10.1016/0166-218X(95)00106-2
[15] M. Knor, R. Škrekovski, and T. Vetrík, Metric dimension of circulant graphs with 5 consecutive generators, Math. 12 (2024), no. 9, Article ID: 1384.  https://doi.org/10.3390/math12091384
[16] D. Kuziak and I.G. Yero, Metric dimension related parameters in graphs: A survey on combinatorial, computational and applied results, arXiv preprint arXiv:2107.04877 (2021).
[17] S. Mashkaria, G. ´Odor, and P. Thiran, On the robustness of the metric dimension of grid graphs to adding a single edge, Discrete Appl. Math. 316 (2022), 1–27. https://doi.org/10.1016/j.dam.2022.02.014
[18] S. Nawaz, M. Ali, M.A. Khan, and S. Khan, Computing metric dimension of power of total graph, IEEE Access 9 (2021), 74550–74561.  https://doi.org/10.1109/ACCESS.2021.3072554
[19] L. Saha, M. Basak, and K. Tiwary, All metric bases and fault-tolerant metric dimension for square of grid, Opuscula Math. 42 (2022), no. 1, 93–111. https://doi.org/10.7494/OpMath.2022.42.1.93
[20] L. Saha, M. Basak, K. Tiwary, K.C. Das, and Y. Shang, On the characterization of a minimal resolving set for power of paths, Math. 10 (2022), no. 14, Article  ID: 2445.  https://doi.org/10.3390/math10142445
[21] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975), 549–559.
[22] R.C. Tillquist, R.M. Frongillo, and M.E. Lladser, Getting the lay of the land in discrete space: A survey of metric dimension and its applications, SIAM Rev. 65 (2023), no. 4, 919–962.  https://doi.org/10.1137/21M1409512
[23] R. Trujillo-Rasua and Ismael G. Yero, k-metric antidimension: A privacy measure for social graphs, Inform. Sci. 328 (2016), 403–417.  https://doi.org/10.1016/j.ins.2015.08.048
[24] J. Wu, L. Wang, and W. Yang, Learning to compute the metric dimension of  graphs, Appl. Math. Comput. 432 (2022), Article ID: 127350. https://doi.org/10.1016/j.amc.2022.127350
[25] S. Zejnilović, J. Gomes, and B. Sinopoli, Network observability and localization of the source of diffusion based on a subset of nodes, 2013 51st Annual Allerton  Conference on Communication, Control, and Computing (Allerton), IEEE, 2013,  pp. 847–852.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 27 February 2025

Files

Share

How to cite

Statistics