metric dimension of $C_n(1‎, ‎2‎, ‎3)$ for $n \equiv 0 \pmod{6}$

Document Type : Original Research Article

Author

Adib Mazandaran Institute of Higher Education, Sari, Iran.

Abstract

The metric dimension of a connected graph $G$ is the minimum number of vertices in a subset $B$ of $G$ such that all other vertices are uniquely determined by their distances to the vertices in $B$. In this case, $B$ is called a metric basis for $G$ and written $dim(G)=\Vert B\Vert$. We have solved an open problem which shows dimension of circulant graph, $dim(C_n(1,2,3))=4, n \equiv 0 \pmod{6}$. To prove this result, we employ a combination of combinatorial techniques, including distance-based analysis and structural properties of circulant graphs, to carefully analyze the relationship between the graphs structure and its metric dimension. The solution not only answers a previously unresolved question in graph theory but also provides valuable insights into the metric dimensions of more general classes of graphs, particularly in network theory, where understanding the metric dimension is essential for applications in sensor networks, graph-based data storage, and network routing. This work lays the groundwork for future research on the metric dimensions of other families of graphs and has potential applications in optimizing communication and sensor placement in large-scale networks.

Keywords

References

 1. F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Combinatoria, 2, 191–195 (1976).
2. M. Imran, A. Q. Baig, S. A. Bokhary, I. Javaid, On the metric dimension of circulant graphs, Applied Mathematics Letters, 25, 320–325 (2012).
3. W. Jia, M. Sun, J. Lian, et al. Feature dimensionality reduction: a review, Complex Intell. Syst., 8, 2663–2693 (2022).
4. M. Mohagheghy Nezhad, F. Rahbarnia, M. Mirzavaziri, R. Ghanbari, A characterization for metric two-dimensional graphs and their enumeration, Journal of Algebraic Systems, 7(2), 179–187 (2020).
5. M. Mohagheghy Nezhad, F. Rahbarnia, M. Mirzavaziri, R. Ghanbari, Solis Graphs and Uniquely Metric Basis Graphs, IJMSI, 17(2), 191–212 (2022).
6. P. J. Slater, Leaves of trees, Proc. 6th Southeastern Conference on Combinatorics, Graph Theory and Computing, Florida Atlantic Univ., Boca Raton, Fla., Congressus Numerantium, 14, 549–559 (1975). 
Analytical and Numerical Solutions for Nonlinear Equations
Volume 8, Issue 2
December 2023
Pages 133-137

Files

History

  • Receive Date: 29 October 2024
  • Revise Date: 23 December 2024
  • Accept Date: 18 January 2025
  • Publish Date: 01 December 2024

Share

How to cite

Statistics