Landmark-Based Localization in OTIS Networks
Khalil Hadi Hakami, Muhammad Faisal Nadeem, Ali Hasan Ahmad, Ali N. A. Koam, Sami Barhoumi · IEEE Access · 2026
Interconnection networks are commonly modeled by graphs in which vertices represent processors or devices and edges represent communication links. In such networks, localization (or identification) of nodes using a small number of reference points is a fundamental task with direct relevance to routing, fault diagnosis, monitoring, and navigation. A standard graph-theoretic measure of this capability is the metric dimension (also called the locating number), defined as the minimum cardinality of a resolving set whose distance-vectors uniquely distinguish all vertices. Because computing the metric dimension is NP-hard in general, determining exact values for structured network families remains an active and practically motivated line of research. In this paper we study the metric dimension of Optical Transpose Interconnection System (OTIS) networks generated from four classical base graphs, the cycle graph, the second power of the path graph, the complete graph, and the star graph. Using distance-structure analysis, symmetry arguments, and carefully constructed resolving sets, we obtain exact metric dimension formulas for these OTIS families.