AUT Journal of Mathematics and Computing

AUT Journal of Mathematics and Computing

On the adjacency dimension of some star related trees

Document Type : Original Article

Authors
Department of Mathematics, Faculty of Science, Imam Khomeini International University, Qazvin, Iran
Abstract
‎Locating or resolving sets are introduced as a graph-theoretic model of robot navigation and has different applications in diverse areas like network discovery‎, ‎computer science and chemistry‎. ‎These applications leads to some graph parameters‎, ‎like the metric dimension and the adjacency dimension‎.‎ A subset $S$ of the vertices of a graph ‎$‎G‎$‎ is an adjacency resolving set for $G$ if for each pair of distinct vertices‎ ‎$x‎, ‎y \in V(G)\setminus S$, there exists $s \in S$ which is adjacent to exactly one of these two vertices‎. ‎An adjacency resolving set with the minimum cardinality is called an adjacency basis and its cardinality is the adjacency dimension of $G$. ‎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 adjacency dimension of some famous star related trees.
Keywords
Subjects

[1]      S. Alikhani and N. Ghanbari, Strong domination number of a modified graph, AUT J. Math. Comput., 5 (2024), pp. 217–223.
[2]      R. C. Brigham, G. Chartrand, R. D. Dutton, and P. Zhang, Resolving domination in graphs, Math. Bohem., 128 (2003), pp. 25–36.
[3]      P. S. Buczkowski, G. Chartrand, C. Poisson, and P. Zhang, On k-dimensional graphs and their bases, Period. Math. Hungar., 46 (2003), pp. 9–15.
[4]      J. Caceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara, and D. R. Wood´ , On the metric dimension of Cartesian products of graphs, SIAM J. Discrete Math., 21 (2007), pp. 423–441.
[5]      I. Charon, O. Hudry, and A. Lobstein, Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard, Theoret. Comput. Sci., 290 (2003), pp. 2109–2120.
[6]      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), pp. 99–113.
[7]      G. Chartrand, V. Saenpholphat, and P. Zhang, The independent resolving number of a graph, Math. Bohem., 128 (2003), pp. 379–393.
[8]      W.-C. Chen, H.-I. Lu, and Y.-N. Yeh, Operations of interlaced trees and graceful trees, Southeast Asian Bull. Math., 21 (1997), pp. 337–348.
[9]      A. Estrada-Moreno, Y. Ram´ırez-Cruz, and J. A. Rodr´ıguez-Velazquez´ , On the adjacency dimension of graphs, Appl. Anal. Discrete Math., 10 (2016), pp. 102–127.
[10]  H. Fernau and J. A. Rodr´ıguez-Velazquez´ , Notions of metric dimension of corona products: combinatorial and computational results, in Computer science—theory and applications, vol. 8476 of Lecture Notes in Comput. Sci., Springer, Cham, 2014, pp. 153–166.
[11]  H. Fernau and J. A. Rodr´ıguez-Velazquez´ , On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results, Discrete Appl. Math., 236 (2018), pp. 183–202.
[12]  J. A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin., 5 (1998), pp. Dynamic Survey 6, 43.
[13]  F. Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969.
[14] F. Harary and R. A. Melter, On the metric dimension of a graph, Ars Combin., 2 (1976), pp. 191–195.
[15]  S. Heidarkhani Gilani, R. Mirzaie, and E. Vatandoost, A remark on the metric dimension in Riemannian manifolds of constant curvature, AUT J. Math. Comput., 6 (2025), pp. 171–176.
[16]  M. Jannesari, Graphs with constant adjacency dimension, Discrete Math. Algorithms Appl., 14 (2022), pp. Paper No. 2150134, 9.
[17]  M. Jannesari and B. Omoomi, The metric dimension of the lexicographic product of graphs, Discrete Math., 312 (2012), pp. 3349–3356.
[18]  M. Johnson, Structure-activity maps for visualizing the graph variables arising in drug design, J Biopharm Stat., 3 (1993), pp. 203–236.
[19]  S. Khuller, B. Raghavachari, and A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math., 70 (1996), pp. 217–229.
[20]  F. Okamoto, B. Phinezy, and P. Zhang, The local metric dimension of a graph, Math. Bohem., 135 (2010), pp. 239–255.
[21]  V. Saenpholphat and P. Zhang, Conditional resolvability in graphs: a survey, Int. J. Math. Math. Sci., (2004), pp. 1997–2017.
[22]  A. Sebo and E. Tannier˝             , On metric generators of graphs, Math. Oper. Res., 29 (2004), pp. 383–393.
[23]  P. J. Slater, Leaves of trees, in Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), Congress. Numer., No. XIV, Utilitas Math., Winnipeg, MB, 1975, pp. 549–559.