The idea of a minimal resolving set has been used in a variety of contexts, including coin weighing, mastermind games, robot navigation, networking, and optimization. An NP-complete problem is determining the connected metric dimension of a given graph. In this study, we determine the exact value of the connected metric dimension for a number of trees, including Y-tree network, subdivision of Y-tree network, F-tree network CT(m, n), a subdivision of the F-tree network and the coconut network  Finally, we derive the explicit formulas for the subdivision of the (n, 2)-fire cracker and the subdivision of the coconut tree S(CT(m, n)).

metric dimension, basis, connected resolving set, subdivision of a graph

Received: July 17, 2024; Revised: September 8, 2024; Accepted: September 30, 2024; Published: November 4, 2024

How to cite this article: Yasser M. Hausawi, Mohammed El-Meligy, Zaid Alzaid, Olayan Alharbi, Badr Almutairi and Basma Mohamed, On some special trees with respect to the connected metric dimension of graphs, Advances and Applications in Discrete Mathematics 41(8) (2024), 697-708. https://doi.org/10.17654/0974165824044

This Open Access Article is Licensed under Creative Commons Attribution 4.0 International License

References:
[1] P. J. Slater, Leaves of trees, Congr. Numer. 14(549-559) (1975), 37.
[2] F. Harary and R. A. Melter, On the metric dimension of a graph, Ars. Combin. 2(191-195) (1976), 1.
[3] Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffmann, M. Mihal’ak and L. S. Ram, Network discovery and verification, IEEE Journal on Selected Areas in Communications 24(12) (2006), 2168-2181.
[4] A. Sebő and E. Tannier, On metric generators of graphs, Mathematics of Operations Research 29(2) (2004), 383-393.
[5] A. Bogomolny and D. Greenwell, Cut the Knot: Invitation to Mastermind, 1999. http://www.maa.org/editorial/knot/Mastermind.html
[6] S. Khuller, B. Raghavachari and A. Rosenfeld, Localization in graphs, Technical Report CS-TR3326 UMIACS, University of Maryland, 1994.
[7] S. U. Rehman, M. Imran and I. Javaid, On the metric dimension of arithmetic graph of a composite number, Symmetry 12(4) (2020), 607.
[8] P. Singh, S. Sharma, S. K. Sharma and V. K. Bhat, Metric dimension and edge metric dimension of windmill graphs, AIMS Mathematics 6(9) (2021), 9138-9153.
[9] H. M. A. Siddiqui and M. Imran, Computing the metric dimension of wheel related graphs, Applied Mathematics and Computation 242 (2014), 624-632.
[10] A. Ahmad, M. Bača and S. Sultan, Computing the metric dimension of kayak paddles graph and cycles with chord, Proyecciones (Antofagasta) 39(2) (2020), 287-300.
[11] V. Saenpholphat and P. Zhang, Connected resolvability of graphs, Czechoslovak Mathematical Journal 53 (2003), 827-840.
[12] L. Eroh, C. X. Kang and E. Yi, The connected metric dimension at a vertex of a graph, Theoretical Computer Science 806 (2020), 53-69.
[13] S. Imran, M. K. Siddiqui, M. Imran, M. Hussain, H. M. Bilal, I. Z. Cheema and Z. Saleem, Computing the metric dimension of gear graphs, Symmetry 10(6) (2018), 209.
[14] M. Dudenko and B. Oliynyk, On unicyclic graphs of metric dimension 2, Algebra Discrete Mathematics 23(2) (2017), 216-222.
[15] G. M. Sundari and K. Murugan, Extra skolem difference mean labeling of some graphs, World Scientific News 145 (2020), 210-221.
[16] U. Vaghela and D. Parmar, Difference perfect square cordial labeling of subdivision of snake graphs, International Journal of Future Generation Communication and Networking 13(2) (2020), 275-297.
[17] V. Ramachandran and C. Sekar, One modulo N gracefulness of regular bamboo tree and coconut tree, International Journal on Applications of Graph Theory in Wireless Ad Hoc Networks and Sensor Networks 6(2) (2014), 1-10.