Structure theory for a characterization of the metric dimension of graphs

Haichang Luo; Ghulam Haidar; Murad ul Islam Khan; Sakander Hayat; Mohammed J. F. Alenazi; Haichang Luo; Ghulam Haidar; Murad ul Islam Khan; Sakander Hayat; Mohammed J. F. Alenazi

doi:10.3934/math.2026249

AIMS Mathematics

2026, Volume 11, Issue 3: 6019-6029. doi: 10.3934/math.2026249

Previous Article Next Article

Research article Special Issues

Structure theory for a characterization of the metric dimension of graphs

1.
Zhanjiang University of Science and Technology, Zhanjiang 524000, Guangdong, China
2.
Department of Mathematics and Statistics, The University of Haripur, Pakistan
3.
Mathematical Sciences, Faculty of Science, Univeriti Brunei Darussalam, Jln Tungku Link, Gadong BE1410, Brunei Darussalam
4.
Department of Computer Engineering, College of Computer and Information Sciences (CCIS), King Saud University, Riyadh 11451, Saudi Arabia

Received: 08 December 2025 Revised: 13 January 2026 Accepted: 29 January 2026 Published: 10 March 2026
MSC : 05C12

Characterizing simple connected graphs of order $ n $ having metric dimension $ n-2 $, solved by Chartrand et al. [Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000), 99-113], is a foundational result in the study of metric dimension. This article presents a refined proof for the non-bipartite case of the original theorem. While this work does not present a new characterization result, its primary contribution is methodological: We reframe the original's lengthy case-by-case elimination argument as a series of standalone lemmas, which we use to formally establish the structural properties that such a graph must satisfy. Building upon these properties, we then provide a direct, constructive proof demonstrating that the graph structure is necessarily the join of a complete and empty graph. This method offers a more elegant argument for this important characterization and also provides a clearer understanding of why this specific graph family emerges.
- graph theory,
- resolvability,
- metric dimension,
- extreme value
Citation: Haichang Luo, Ghulam Haidar, Murad ul Islam Khan, Sakander Hayat, Mohammed J. F. Alenazi. Structure theory for a characterization of the metric dimension of graphs[J]. AIMS Mathematics, 2026, 11(3): 6019-6029. doi: 10.3934/math.2026249

Related Papers:

Abstract

Characterizing simple connected graphs of order $ n $ having metric dimension $ n-2 $, solved by Chartrand et al. [Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000), 99-113], is a foundational result in the study of metric dimension. This article presents a refined proof for the non-bipartite case of the original theorem. While this work does not present a new characterization result, its primary contribution is methodological: We reframe the original's lengthy case-by-case elimination argument as a series of standalone lemmas, which we use to formally establish the structural properties that such a graph must satisfy. Building upon these properties, we then provide a direct, constructive proof demonstrating that the graph structure is necessarily the join of a complete and empty graph. This method offers a more elegant argument for this important characterization and also provides a clearer understanding of why this specific graph family emerges.

References

[1]	P. J. Slater, Leaves of trees, Congr. Numer. 14 (1975), 549–559.
[2]	F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Combin., 2 (1976), 191–195.
[3]	R. C. Tillquist, R. M. Frongillo, M. E. Lladser, Getting the lay of the land in discrete space: a survey of metric dimension and its applications, SIAM Rev., 65 (2023), 919–962. https://doi.org/10.1137/21M1409512 doi: 10.1137/21M1409512
[4]	A. El-Mesady, Y. S. Hamed, K. M. Abualnaja, A novel application on mutually orthogonal graph squares and graph-orthogonal arrays, AIMS Math., 7 (2022), 7349–7373. https://doi.org/10.3934/math.2022410 doi: 10.3934/math.2022410
[5]	A. El-Mesady, O. Bazighifan, Q. Al-Mdallal, On infinite circulant-balanced complete multipartite graphs decompositions based on generalized algorithmic approaches, Alex. Eng. J., 61 (2022), 11267–11275. https://doi.org/10.1016/j.aej.2022.04.022 doi: 10.1016/j.aej.2022.04.022
[6]	F. Bullo, J. Cortés, F. Dörfler, S. Martínez, Lectures on network systems, CreateSpace, 2018.
[7]	Q. K. Meng, H. Yang, B. Jiang, Q. Tang, X. L. Zhang, Accessibility, observability, and fault-tolerant control structure selection of network nonlinear systems, IEEE Trans. Control Netw. Syst., 9 (2022), 75–87. https://doi.org/10.1109/TCNS.2022.3141693 doi: 10.1109/TCNS.2022.3141693
[8]	G. Chartrand, L. Eroh, M. A. Johnson, O. R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math., 105 (2000), 99–113. https://doi.org/10.1016/S0166-218X(00)00198-0 doi: 10.1016/S0166-218X(00)00198-0

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)