Answers are grounded in this paper and cite their sources.
Consider a robot that is trying to determine its current location while navigating a graph-based environment. To know how distant it is from each group of fixed landmarks, it can send a signal. We handle the problem of precisely identifying the minimum number of landmarks needed and their ideal placement to guarantee the robot can always discover itself. The number of landmarks in the graph is its metric dimension, and the collection of nodes on which they are distributed is its metric basis. The smallest group of nodes required to uniquely identify each other node in a graph using shortest path distances is known as the metric dimension of the graph. We consider the NP-hard problem of finding the metric dimension of graphs. A set of vertices B of a connected graph G resolves G if every vertex of G is uniquely identified by its vector of distances to the vertices in B. The minimum resolving set is called the metric basis and the cardinality of the basis is called the metric dimension of G. Metric dimension has applications in a wide range of areas such as robot navigation, telecommunications, combinatorial optimization, and pharmacocatual chemistry. In this paper, we determine the metric dimension of the family of alternate snake graphs including alternate snake, alternate k-polygonal snake, double alternate triangular snake and triple alternate triangular snake graph.
No takes yet. Share an insight, caveat, or question.
Mohamed et al. (2023) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: