The adjacency dimension of some path related trees

Document Type : Research Paper

Authors

Department of Mathematics, Faculty of Science, Imam Khomeini International University, P.O. Box: 34149-16818, Qazvin, Iran

Abstract

‎Since the problem of computing the adjacency dimension of a graph is NP-hard‎, ‎finding the adjacency dimension of special classes of graphs or obtaining good bounds on this invariant is valuable‎. ‎In this paper we determine the properties of each adjacency resolving set of paths. ‎Then, ‎by ‎using ‎these ‎properties,‎ we determine the adjacency dimension of broom and double broom graphs‎.

Keywords

Main Subjects

References

[1] Brigham, R.C., Chartrand, G., Dutton, R.D., & Zhang, P. (2003). Resolving domination in graphs. Math. Bohem., 128(1), 25-36. https://doi.org/10.21136/mb.2003.133935
[2] Buczkowski, P.S., Chartrand, G., Poisson, C., & Zhang, P. (2003). On k-dimensional graphs and their bases. Period. Math. Hung., 46(1), 9-15. https://doi.org/10.1023/A:1025745406160
[3] Caceres, J., Hernando, C., Mora, M., Pelayo, I.M., Puertas, M.L., Seara, C., & Wood, D.R. (2007). On the metric dimension of Cartesian product of graphs. SIAM J. Discrete Math., 21(2), 423-441. https://doi.org/10.1137/050641867
[4] Charon, I., Hudry, O., & Lobstein, A. (2003). Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard. Theoret. Comput. Sci., 290(3), 2109-2120. https://doi.org/10.1016/s0304-3975(02)00536-4
[5] Chartrand, G., Eroh, L., Johnson, M. A., & Oellermann, O. (2000). Resolvability in Graphs and the Metric Dimension of a Graph. Discrete Appl. Math., 105(3), 99-113. https://doi.org/10.1016/s0166-218x(00)00198-0
[6] Chartrand, G., Saenpholphat, V., & Zhang, P. (2003). The independent resolving number of a graph. Math. Bohem., 128(4), 379-393. https://doi.org/10.21136/mb.2003.134003
[7] Estrada-Moreno, A., Ramrez-Cruz, Y., & Rodriguez-Velazquez, J. A. (2016). On the adjacency dimension of graphs. Appl. Anal. Discrete Math., 10(1), 102-127. https://doi.org/10.2298/aadm151109022e
[8] Fernau, H., & Rodriguez-Velazquez, J. A. (2014). Notions of metric dimension of corona products: combinatorial and computational results, in: Computer science theory and applications. Springer, Cham, Lect. Notes Comput. Sci., 84(1), 153-
166. https://doi.org/10.1007/978-3-319-06686-8
[9] Fernau, H., & Rodriguez-Velazquez, J. A. (2018). On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results. Discrete Appl. Math., 23(6), 183-202.
https://doi.org/10.1016/j.dam.2017.11.019
[10] Harary, F. (1969). Graph Theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London.
[11] Harary, F., & Melter, R. A. (1976). On the Metric Dimension of a Graph. Ars Combin., 2(1), 191-195.
[12] Haynes, T.W., Henning, M.A., & Howard, J. (2006). Locating and total dominating sets in trees. Discrete Appl. Math., 154(8), 1293-1300. https://doi.org/10.1016/j.dam.2006.01.002
[13] Iswadi, H., Baskoro, E.T., & Simanjuntak, R. (2011). On the metric dimension of corona product of graphs. Far East J. Math. Sci., 52(2), 155-170. http://pphmj.com/journals/fjms.htm
[14] Jannesari, M. (2023). On lower bounds for the metric dimension of graphs. J. Mahani math. res., 12(1), 35-41. https://doi.org/10.22103/jmmrc.2022.19121.1211
[15] Jannesari, M. (2024). Metric dimension of lexicographic product of some known graphs. J. Mahani math. res., 13(1), 269-277. https://doi.org/10.22103/jmmr.2023.20814.1384
[16] Jannesari, M., & Omoomi, B. (2012). The metric dimension of the lexicographic product of graphs. Discrete Math., 312(22), 3349-3356. https://doi.org/10.1016/j.disc.2012.07.025
[17] Jannesari, M. (2022). Graphs with constant adjacency dimension. Discrete Math. Algorithms Appl., 14(4), 1-12. https://doi.org/10.1142/s1793830921501342
[18] Johnson, M. (1993). Structure{activity maps for visualizing the graph variables arising in drug design. J. Biopharm. Statist., 3(2), 203-236. https://doi.org/10.1080/10543409308835060
[19] Khuller, S., Raghavachari, B., & Rosenfeld, A. (1996). Landmarks in graphs. Discrete Appl. Math., 70(1), 217-229. https://doi.org/10.1016/0166-218x(95)00106-2
[20] Okamoto, F., Phinezy, B., & Zhang, P. (2010). The local metric dimension of a graph. Math. Bohem., 135(3), 239-255. https://doi.org/10.21136/mb.2010.140702
[21] Rodrguez-Velazquez, J. A., & Fernau, H. (2018). On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results. Discrete Appl. Math., 236(1), 183-202.
https://doi.org/10.1016/j.dam.2017.11.019
[22] Saenpholphat, V., & Zhang, P. (2004). Conditional resolvability in graphs: a survey. Int. J. Math. Math. Sci., 38(2), 1997-2017. https://doi.org/10.1155/s0161171204311403
[23] Sebo, A., & Tannier, E. (2004). On metric generators of graphs. Math. Oper. Res., 29(2), 383-393. https://doi.org/10.1287/moor.1030.0070
[24] Slater, P.J. (1975). Leaves of trees. Congr. Numer., 14(1), 549-559.
[25] Yero, I.G., Kuziak, D., & Rodriquez-Velazquez, J.A. (2011). On the metric dimension of corona product graphs. Comput. Math. Appl., 61(9), 2793-2798. https://doi.org/10.1016/j.camwa.2011.03.046
Journal of Mahani Mathematical Research
Volume 14, Issue 1 - Serial Number 31
January 2025
Pages 369-386

Files

History

  • Receive Date: 30 January 2024
  • Revise Date: 28 September 2024
  • Accept Date: 01 November 2024

Share

How to cite

Statistics