Malaysian Journal of Mathematical Sciences, December 2025, Vol. 19, No. 4
Metric Dimension of 4-Regular Cyclic Bipartite Graphs
Bharani Dharan, K. and Radha, S.
Corresponding Email: radha.s@vit.ac.in
Received date: 9 February 2024
Accepted date: 28 May 2025
Abstract:
The metric dimension of a graph, denoted by $\dim(G)$, represents the minimum number of landmarks required to uniquely identify all vertices based on their distances to these landmarks. This parameter plays a crucial role in interconnection networks, facilitating applications such as efficient routing and system verification. Cyclic bipartite graphs, which model systems with periodic structures like communication rings and circular sensor networks, present particular challenges due to their inherent symmetry. Determining the metric dimension in such graphs is essential for efficient vertex identification and resource optimization. In this paper, we compute the metric dimension of 4-regular cyclic bipartite graphs, denoted by $CB_{4,n}$. Specifically, for all $n \geq 5$, we establish that $\dim(CB_{4,n}) = 4$ when $n \not\equiv 1 \pmod{3}$, and $\dim(CB_{4,n}) = 5$ when $n \equiv 1 \pmod{3}$, thus providing a precise characterization based on graph parameters. These findings not only advance the theoretical understanding of cyclic bipartite structures, but also offer practical implications for the design of robust network topologies, optimal sensor placement in cyclic environments, and efficient localization in robotics and surveillance systems. By minimizing the number of required landmarks, our results contribute significantly to the optimization of resource allocation in structured and repetitive networks.
Keywords: cyclic bipartite graphs; resolving set; metric basis; metric dimension
