On metric dimension of cube of trees

Paul, Sanchita; Das, Bapan; Adhikari, Avishek; Saha, Laxman

doi:10.22049/cco.2025.29750.2143

تعداد نشریات	6
تعداد شماره‌ها	131
تعداد مقالات	1,634
تعداد مشاهده مقاله	1,900,304
تعداد دریافت فایل اصل مقاله	1,759,692

	On metric dimension of cube of trees
Communications in Combinatorics and Optimization
مقاله 13، دوره 12، شماره 1، خرداد 2027، صفحه 185-211 اصل مقاله (571.1 K)
نوع مقاله: Original paper
شناسه دیجیتال (DOI): 10.22049/cco.2025.29750.2143
نویسندگان
Sanchita Paul^* ¹؛ Bapan Das²؛ Avishek Adhikari³؛ Laxman Saha⁴
¹Department of Mathematics, C.V. Raman Global University, Bhubaneswar 752054, India
²Department of Mathematics, Balurghat College, Balurghat 733101, India
³Department of Mathematics, Presidency University, Kolkata 700073, India
⁴Department of Mathematics, Balurghat College, Balurghat 733101, India
چکیده
Let $G=(V,E)$ be a connected graph and $d_{G}(u,v)$ be the shortest distance between the vertices $u$ and $v$ in $G$. A set $S=\{s_{1},s_{2},\dots,s_{n}\}\subset V(G)$ is said to be a {\em resolving set} if for all distinct vertices $u,v$ of $G$, there exists an element $s\in S$ such that $d_{G}(s,u)\neq d_{G}(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 $\beta{(G)}$. A resolving set having $\beta{(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 $T^{3}=(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 $T^{3}$. This helps to determine the tight bounds (upper and lower) on the metric dimension of $T^{3}$. 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 $\beta{(T^{3})}=\beta{(T)}$.
کلیدواژه‌ها
resolving set؛ metric basis؛ metric dimension؛ trees

مراجع
[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.
آمار تعداد مشاهده مقاله: 492 تعداد دریافت فایل اصل مقاله: 400

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب

پیوندهای مفید

آمار

On metric dimension of cube of trees