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,yV(G)S, there exists sS 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

Main Subjects