Metric dimension of line graphs of optimal fault-tolerant token ring networks

Asma Alasmri; Nor Muhainiah Mohd Ali; Ali Ahmad; Muhammad Faisal Nadeem; Asma Alasmri; Nor Muhainiah Mohd Ali; Ali Ahmad; Muhammad Faisal Nadeem

doi:10.3934/math.2026299

AIMS Mathematics

2026, Volume 11, Issue 3: 7264-7284. doi: 10.3934/math.2026299

Previous Article Next Article

Research article

Metric dimension of line graphs of optimal fault-tolerant token ring networks

1.
Department of Mathematical Sciences, Faculty of Science, Universiti Teknologi Malaysia, UTM Johor Bahru 81310, Johor, Malaysia
2.
Department of Computer Science, College of Engineering and Computer Science, Jazan University, Jazan, Saudi Arabia
3.
Department of Mathematics, COMSATS University Islamabad, Lahore Campus 54000, Pakistan

Received: 20 January 2026 Revised: 07 March 2026 Accepted: 09 March 2026 Published: 19 March 2026
MSC : 05C12, 05C90

Interconnection networks are commonly modeled as graphs, where vertices represent processors or devices and edges represent communication links. In such networks, locating or identifying components using a small set of reference points is fundamental for routing, fault diagnosis, monitoring, and navigation. A standard graph-theoretic measure of this capability is the metric dimension (or locating number), defined as the minimum cardinality of a resolving set whose distance vectors uniquely distinguish all vertices. Since determining the metric dimension is NP-hard in general, exact values for structured network families are of both theoretical and practical interest. In this paper, we studied the metric dimension of the line graph of an optimal $ 2 $-fault-tolerant token ring network. The underlying network $ \mathbb{T}_{m}^{2} $ augments a simple ring with additional links to ensure robust connectivity under up to two link or node failures, while the line graph $ L(\mathbb{T}_{m}^{2}) $ represents the network at the link level. A lemma was established to prove the lower bound of the metric dimension via contradiction, while the upper bound was determined by explicitly constructing resolving sets. The analysis was conducted case by case according to the congruence of the network order modulo $ 4 $, which simplified verification of all representation vectors. Our results showed that the fault-tolerant links increase the metric dimension compared with ordinary token rings, highlighting the influence of additional links on network distinguishability and providing insights for the design of robust interconnection networks.
- metric dimension,
- line graph,
- resolving set,
- token ring network,
- fault-tolerant network
Citation: Asma Alasmri, Nor Muhainiah Mohd Ali, Ali Ahmad, Muhammad Faisal Nadeem. Metric dimension of line graphs of optimal fault-tolerant token ring networks[J]. AIMS Mathematics, 2026, 11(3): 7264-7284. doi: 10.3934/math.2026299

Related Papers:

Abstract

Interconnection networks are commonly modeled as graphs, where vertices represent processors or devices and edges represent communication links. In such networks, locating or identifying components using a small set of reference points is fundamental for routing, fault diagnosis, monitoring, and navigation. A standard graph-theoretic measure of this capability is the metric dimension (or locating number), defined as the minimum cardinality of a resolving set whose distance vectors uniquely distinguish all vertices. Since determining the metric dimension is NP-hard in general, exact values for structured network families are of both theoretical and practical interest. In this paper, we studied the metric dimension of the line graph of an optimal $ 2 $-fault-tolerant token ring network. The underlying network $ \mathbb{T}_{m}^{2} $ augments a simple ring with additional links to ensure robust connectivity under up to two link or node failures, while the line graph $ L(\mathbb{T}_{m}^{2}) $ represents the network at the link level. A lemma was established to prove the lower bound of the metric dimension via contradiction, while the upper bound was determined by explicitly constructing resolving sets. The analysis was conducted case by case according to the congruence of the network order modulo $ 4 $, which simplified verification of all representation vectors. Our results showed that the fault-tolerant links increase the metric dimension compared with ordinary token rings, highlighting the influence of additional links on network distinguishability and providing insights for the design of robust interconnection networks.

References

[1]	J. A. Bondy, U. S. R. Murty, Graph theory with applications, Macmillan, 1976.
[2]	D. B. West, Introduction to graph theory, Prentice Hall, 2001.
[3]	IEEE, IEEE standard for information technology—token ring access method and physical layer specifications, IEEE Std 802.5, 1989.
[4]	R. Metcalfe, D. R. Boggs, Ethernet: distributed packet switching for local computer networks, Commun. ACM, 19 (1976), 395–404. https://doi.org/10.1145/360248.360253 doi: 10.1145/360248.360253
[5]	J. Duato, S. Yalamanchili, L. Ni, Interconnection networks: an engineering approach, Morgan Kaufmann Publishers Inc., 2003. https://doi.org/10.5555/572400
[6]	T. Haynes, S. Hedetniemi, P. Slater, Foundations of interconnection networks, Wiley, 1999.
[7]	P. J. Slater, Leaves of trees, Congressus Numerantium, 14 (1975), 549–559.
[8]	P. J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci., 22 (1988), 445–455.
[9]	F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Comb., 1976 (1976), 191–195.
[10]	R. A. Melter, I. Tomescu, Metric bases in digital geometry, Comput. Vision Graphics Image Process., 25 (1984), 113–121. https://doi.org/10.1016/0734-189X(84)90051-3 doi: 10.1016/0734-189X(84)90051-3
[11]	S. Khuller, B. Raghavachari, A. Rosenfeld, Localization in graphs, Technical Report UMIACS-TR-94-92, University of Maryland, Institute for Advanced Computer Studies, 1994.
[12]	J. Kratica, V. Kovačević-Vujčić, M. Čangalović, M. Stojanović, Minimal doubly resolving sets and the strong metric dimension of some convex polytopes, Appl. Math. Comput., 218 (2012), 9790–9801. https://doi.org/10.1016/j.amc.2012.03.047 doi: 10.1016/j.amc.2012.03.047
[13]	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
[14]	M. Imran, A. Q. Baig, S. A. U. H. Bokhary, I. Javaid, On the metric dimension of circulant graphs, Appl. Math. Lett., 25 (2012), 320–325. https://doi.org/10.1016/j.aml.2011.09.008 doi: 10.1016/j.aml.2011.09.008
[15]	M. Imran, M. K. Siddiqui, R. Naeem, On the metric dimension of generalized petersen multigraphs, IEEE Access, 6 (2018), 74328–74338. https://doi.org/10.1109/ACCESS.2018.2883556 doi: 10.1109/ACCESS.2018.2883556
[16]	I. G. Yero, D. Kuziak, J. A. Rodríguez-Velázquez, On the metric dimension of corona product graphs, Comput. Math. Appl., 61 (2011), 2793–2798. https://doi.org/10.1016/j.camwa.2011.03.046 doi: 10.1016/j.camwa.2011.03.046
[17]	A. Szolnoki, M. Perc, Correlation of positive and negative reciprocity fails to confer an evolutionary advantage: phase transitions to elementary strategies, Phys. Rev. X, 3 (2013), 041021. https://doi.org/10.1103/PhysRevX.3.041021 doi: 10.1103/PhysRevX.3.041021
[18]	R. Naeem, M. Imran, On resolvability and exchange property in antiweb-wheels, Utilitas Math., 104 (2017), 187–200.
[19]	M. Perc, J. Gómez-Gardeñes, A. Szolnoki, L. M. Floría, Y. Moreno, Evolutionary dynamics of group interactions on structured populations: a review, J. R. Soc. Interface, 10 (2013), 0997. https://doi.org/10.1098/rsif.2012.0997 doi: 10.1098/rsif.2012.0997
[20]	M. Ali, M. T. Rahim, G. Ali, On path related graphs with constant metric dimension, Utilitas Math., 88 (2012), 203–209. https://doi.org/10.1155/2021/2085778 doi: 10.1155/2021/2085778
[21]	M. M. Alholi, O. A. Abughneim, H. A. Ezeh, Metric dimension of some path related graphs, Global J. Pure Appl. Math., 3 (2017), 149–157.
[22]	A. T. Shahida, M. S. Sunitha, On the metric dimension of joins of two graphs, Global J. Pure Appl. Math., 5 (2014), 33–38.
[23]	H. Pan, M. Ali, G. Ali, M. T. Ali, X. Yang, On the families of graphs with unbounded metric dimension, IEEE Access, 7 (2019), 165060–165064. https://doi.org/10.1109/ACCESS.2019.2952192 doi: 10.1109/ACCESS.2019.2952192
[24]	H. Peng, X. Wang, J. Wang, J. Chen, On the metric dimension of some kneser graphs, J. Comput. Theor. Nanosci., 13 (2016), 3013–3018.
[25]	M. F. Nadeem, W. Ali, H. M. A. Siddiqui, Locating number of biswapped networks, Int. J. Found. Comput. Sci., 33 (2022), 667–690. https://doi.org/10.1142/S0129054122420096 doi: 10.1142/S0129054122420096
[26]	M. Arulperumjothi, S. Klavžar, S. Prabhu, Redefining fractal cubic networks and determining their metric dimension and fault-tolerant metric dimension, Appl. Math. Comput., 452 (2023), 128037. https://doi.org/10.1016/j.amc.2023.128037 doi: 10.1016/j.amc.2023.128037
[27]	T. Vetrík, M. Imran, M. Knor, R. Škrekovski, The metric dimension of the circulant graph with $2k$ generators can be less than $k$, J. King Saud Univ. Sci., 35 (2023), 102834. https://doi.org/10.1016/j.jksus.2023.102834 doi: 10.1016/j.jksus.2023.102834
[28]	A. Hakanen, V. Junnila, T. Laihonen, I. G. Yero, On the unicyclic graphs having vertices that belong to all their (strong) metric bases, Discrete Appl. Math., 353 (2024), 191–207. https://doi.org/10.1016/j.dam.2024.04.020 doi: 10.1016/j.dam.2024.04.020
[29]	B. Assiri, M. F. Nadeem, W. Ali, A. Ahmad, Fault-tolerance in biswapped multiprocessor interconnection networks, J. Parallel Distrib. Comput., 196 (2025), 105009. https://doi.org/10.1016/j.jpdc.2024.105009 doi: 10.1016/j.jpdc.2024.105009
[30]	K. Nie, K. Xu, The doubly metric dimensions of cactus graphs and block graphs, J. Comb. Optim., 47 (2024), 120–134. https://doi.org/10.1007/s10878-024-01168-0 doi: 10.1007/s10878-024-01168-0
[31]	L. S. Mhagama, M. N. Husin, M. F. Nadeem, W. Ali, Computing the edge metric dimension of the line graph of the molec-ular graphs of some classes of antiviral drugs, with focus on mpox treatments, Contemp. Math., 6 (2025), 1784–1802. https://doi.org/10.37256/cm.6220255898 doi: 10.37256/cm.6220255898
[32]	D. Dolžan, M. Koš, Metric dimension in semiring total graphs, Mediterr. J. Math., 22 (2025), 112.
[33]	S. Nazeer, M. Hussain, A. ur Rehman, A. H. Ali, On metric dimension of symmetrical planar pyramid related graphs, Afr. Mat., 36 (2025), 54. https://doi.org/10.1007/s13370-025-01253-5 doi: 10.1007/s13370-025-01253-5
[34]	A. Khan, S. Ali, S. Hayat, M. Azeem, Y. Zhong, M. A. Zahid, et al., Fault-tolerance and unique identification of vertices and edges in a graph: the fault-tolerant mixed metric dimension, J. Parallel Distrib. Comput., 197 (2025), 105024. https://doi.org/10.1016/j.jpdc.2024.105024 doi: 10.1016/j.jpdc.2024.105024
[35]	K. Azhar, A. Nadeem, Y. Shang, Fault-tolerant metric dimension in carbon networks, Foundations, 5 (2025), 13. https://doi.org/10.3390/foundations5020013 doi: 10.3390/foundations5020013
[36]	M. Knor, J. Sedlar, R. Škrekovski, Fault tolerance of metric basis can be expensive, Mediterr. J. Math., 22 (2025), 148. https://doi.org/10.1007/s00009-025-02894-3 doi: 10.1007/s00009-025-02894-3
[37]	B. Mohamed, Metric dimension of graphs and its application to robotic navigation, Int. J. Comput. Appl., 184 (2022), 15. https://doi.org/10.5120/ijca2022922090 doi: 10.5120/ijca2022922090
[38]	S. Hayat, R. Naeem, H. M. A. Siddiqui, A. Riaz, M. Imran, M. B. Belay, et al., Metric, edge-metric, mixed-metric, and fault-tolerant metric dimensions of geometric networks with potential applications, Sci. Rep., 15 (2025), 41035. https://doi.org/10.1038/s41598-025-24939-z doi: 10.1038/s41598-025-24939-z
[39]	M. Feng, M. Xu, K. Wang, On the metric dimension of line graphs, Discrete Appl. Math., 161 (2013), 802–805. https://doi.org/10.1016/j.dam.2012.10.018 doi: 10.1016/j.dam.2012.10.018
[40]	L. Eroh, S. Kang, H. Yi, Metric dimension and zero forcing number of line graphs of wheel graphs and bouquet graphs, AKCE Int. J. Graphs Comb., 15 (2018), 267–273. https://doi.org/10.21136/MB.2014.143937 doi: 10.21136/MB.2014.143937
[41]	M. U. Farooq, A. Rehman, T. Q. Ibrahim, M. Hussain, A. H. Ali, B. Rashwani, Metric dimension of line graphs of Bakelite and subdivided Bakelite network, Discrete Dyn. Nat. Soc., 2023 (2023), 7656214. https://doi.org/10.1155/2023/7656214 doi: 10.1155/2023/7656214
[42]	J. Wu, L. Wang, W. Yang, Learning to compute the metric dimension of graphs, Appl. Math. Comput., 432 (2022), 127350. https://doi.org/10.1016/j.amc.2022.127350 doi: 10.1016/j.amc.2022.127350
[43]	A. Khan, G. Haidar, N. Abbas, M. U. I. Khan, A. U. K. Niazi, A. U. I. Khan, Metric dimensions of bicyclic graphs, Mathematics, 11 (2023), 869. https://doi.org/10.3390/math11040869 doi: 10.3390/math11040869
[44]	Pranjali, A. Kumar, R. Sharma, Metric dimension of unit graphs, Discrete Math. Algorithms Appl., 17 (2025), 2450057. https://doi.org/10.1142/S1793830924500575 doi: 10.1142/S1793830924500575
[45]	L. S. Mhagama, M. N. Husin, M. F. Nadeem, W. Ali, On the edge metric dimension of some families of splitting graphs, Discrete Math. Algorithms Appl., 9 (2025), 2550061. https://doi.org/10.1142/S1793830925500612 doi: 10.1142/S1793830925500612
[46]	S. Vidya, S. K. Sharma, P. Poojary, G. R. V. Bhatta, Metric basis and metric dimension of some infinite planar graphs, Discrete Math. Algorithms Appl., 16 (2024), 2450076. https://doi.org/10.1142/S1793830924500769 doi: 10.1142/S1793830924500769
[47]	T. Y. Sung, T. Y. Ho, C. P. Chang, L. H. Hsu, Optimal k-fault-tolerant networks for token rings, J. Inf. Sci. Eng., 16 (2000), 381–390.

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)