Characterizing edge-based doubly resolving sets within circulant networks $ C_n(1, 2) $

Ruby Nasir; Muhammad Ahmad; Zohaib Zahid; Sanaa A. Bajri; Hamiden Abd El-Wahed Khalifa; Ruby Nasir; Muhammad Ahmad; Zohaib Zahid; Sanaa A. Bajri; Hamiden Abd El-Wahed Khalifa

doi:10.3934/math.2024766

AIMS Mathematics

2024, Volume 9, Issue 6: 15857-15874. doi: 10.3934/math.2024766

Previous Article Next Article

Research article Special Issues

Characterizing edge-based doubly resolving sets within circulant networks $ C_n(1, 2) $

1.
Department of Mathematics, University of Management and Technology, Lahore 54000, Pakistan
2.
Department of Mathematical Sciences, College of Science, Princess Nourah bint Abdulrahman University, P.O. Box 84428, Riyadh 11671, Saudi Arabia
3.
Department of Mathematics, College of Science, Qassim University, Buraydah 51452, Saudi Arabia
4.
Department of Operations and Management Research, Faculty of Graduate Studies for Statistical Research, Cairo University, Giza 12613, Egypt

Received: 22 February 2024 Revised: 22 April 2024 Accepted: 25 April 2024 Published: 06 May 2024
MSC : 05C12

The focus of this article lies on the notion of the edge version of doubly resolving sets (EVDRSs) in circulant networks. EVDRSs refer to unique edge subsets that are necessary for identifying individual edges in a network and distinguishing them based on their edge distances to the elements of the EVDRS. The main objectives were to define the minimal size of EVDRSs for circulant networks $ C_n(1, 2) $ and to investigate their basic properties. The systematic research helped to achieve a new understanding of the existence, construction, and characterization of EVDRSs in circulant networks $ C_n(1, 2) $. It is established that the EVDRSs in the circulant network $ C_n(1, 2) $ are finite and are bounded by the order of the network. Among the numerous implications of these findings are those that refer to the design and optimization of distributed sensor networks, improving communication and network protocols, as well as tracking the spread of infectious diseases and epidemics over social networks. The application of the identified methodology helps improve the process of network optimization which contributes to the development of more effective and robust circulant-based structures.
- complex networks,
- circulant networks,
- edge computing,
- optimization,
- metric dimension,
- doubly resolving sets
Citation: Ruby Nasir, Muhammad Ahmad, Zohaib Zahid, Sanaa A. Bajri, Hamiden Abd El-Wahed Khalifa. Characterizing edge-based doubly resolving sets within circulant networks $ C_n(1, 2) $[J]. AIMS Mathematics, 2024, 9(6): 15857-15874. doi: 10.3934/math.2024766

Related Papers:

Abstract

The focus of this article lies on the notion of the edge version of doubly resolving sets (EVDRSs) in circulant networks. EVDRSs refer to unique edge subsets that are necessary for identifying individual edges in a network and distinguishing them based on their edge distances to the elements of the EVDRS. The main objectives were to define the minimal size of EVDRSs for circulant networks $ C_n(1, 2) $ and to investigate their basic properties. The systematic research helped to achieve a new understanding of the existence, construction, and characterization of EVDRSs in circulant networks $ C_n(1, 2) $. It is established that the EVDRSs in the circulant network $ C_n(1, 2) $ are finite and are bounded by the order of the network. Among the numerous implications of these findings are those that refer to the design and optimization of distributed sensor networks, improving communication and network protocols, as well as tracking the spread of infectious diseases and epidemics over social networks. The application of the identified methodology helps improve the process of network optimization which contributes to the development of more effective and robust circulant-based structures.

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]	M. Idrees, H. Ma, M. Wu, A. R. Nizami, M. Munir, S. Ali, Metric dimension of generalized Mobius ladder and its application to wsn localization, J. Adv. Comput. Intell., 24 (2020), 3–11. https://doi.org/10.20965/jaciii.2020.p0003 doi: 10.20965/jaciii.2020.p0003
[4]	S. Soderberg, H. S. Shapiro, A combinatory detection problem, Am. Math. Mon., 70 (1963), 1066–1070. https://doi.org/10.1080/00029890.1963.11992174 doi: 10.1080/00029890.1963.11992174
[5]	A. Sebo, E. Tannier, On metric generators of graphs, Math. Oper. Res., 29 (2004), 191–406. https://doi.org/10.1287/moor.1030.0070 doi: 10.1287/moor.1030.0070
[6]	S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math., 70 (1996), 217–229. https://doi.org/10.1016/0166-218X(95)00106-2 doi: 10.1016/0166-218X(95)00106-2
[7]	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
[8]	M. Ali, G. Ali, U. Ali, M. T. Rahim, On cycle related graphs with constant metric dimension, Open J. Discrete Math., 2 (2012), 21–23. https://doi.org/10.4236/ojdm.2012.21005 doi: 10.4236/ojdm.2012.21005
[9]	M. R. Garey, D. S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, 1990, 37–79.
[10]	D. T. Murdiansyah, Adiwijaya, Computing the metric dimension of hypercube graphs by particle swarm optimization algorithms, In: Recent advances on soft computing and data mining: The second international conference on soft computing and data mining (SCDM-2016), Cham: Springer, 2016. https://doi.org/10.1007/978-3-319-51281-5_18
[11]	H. Fernau, P. Heggernes, P. Van't Hof, D. Meistera, R. Saei, Computing the metric dimension for chain graphs, Inform. Process. Lett., 115 (2015), 671–676. https://doi.org/10.1016/j.ipl.2015.04.006 doi: 10.1016/j.ipl.2015.04.006
[12]	M. Mulyono, W. Wulandari, The metric dimension of friendship graph Fn, lollipop graph $L(m, n)$ and petersen graph $P(n, m)$, Bull. Math., 8 (2016), 117–124.
[13]	F. S. Raj, A. George, On the metric dimension of silicate stars, ARPN J. Eng. Appl. Sci., 10 (2015), 2187–2192.
[14]	S. Hayat, A. Khan, Y. Zhong, On resolvability- and domination-related parameters of complete multipartite graphs, Mathematics, 10 (2022), 1815. https://doi.org/10.3390/math10111815 doi: 10.3390/math10111815
[15]	P. Manuel, B. Rajan, I. Rajasingh, C. Monica, On minimum metric dimension of honeycomb networks, J. Discret. Algorit., 6 (2008), 20–27. https://doi.org/10.1016/j.jda.2006.09.002 doi: 10.1016/j.jda.2006.09.002
[16]	S. Hayat, A. Khan, M. Y. H. Malik, M. Imran, M. K. Siddiqui, Fault-tolerant metric dimension of interconnection networks, IEEE Access, 8 (2020), 145435–145445. https://doi.org/10.1109/ACCESS.2020.3014883 doi: 10.1109/ACCESS.2020.3014883
[17]	L. Saha, K. Tiwary, K. C. Das, Y. Shang, Optimal multi-level fault-tolerant resolving sets of circulant graph $C_n(1, 2)$, Mathematics, 11 (2023), 1896. https://doi.org/10.3390/math11081896 doi: 10.3390/math11081896
[18]	H. Raza, S. Hayat, X. F. Pan, On the fault-tolerant metric dimension of convex polytopes, Appl. Math. Comput., 339 (2018), 172–185. https://doi.org/10.1016/j.amc.2018.07.010 doi: 10.1016/j.amc.2018.07.010
[19]	H. M. A. Siddiqui, S. Hayat, A. Khan, M. Imran, A. Razzaq, J. B. Liu, Resolvability and fault-tolerant resolvability structures of convex polytopes, Theor. Comput. Sci., 796 (2019), 114–128. https://doi.org/10.1016/j.tcs.2019.08.032 doi: 10.1016/j.tcs.2019.08.032
[20]	L. Saha, R. Lama, K. Tiwary, K. C. Das, Y. Shang, Fault-tolerant metric dimension of circulant graphs, Mathematics, 10 (2022), 124. https://doi.org/10.3390/math10010124 doi: 10.3390/math10010124
[21]	H. Raza, S. Hayat, M. Imran, X. F. Pan, Fault-tolerant resolvability and extremal structures of graphs, Mathematics, 7 (2019), 78. https://doi.org/10.3390/math7010078 doi: 10.3390/math7010078
[22]	L. Saha, M. Basak, K. Tiwary, K. C. Das, Y. Shang, On the characterization of a minimal resolving set for power of paths, Mathematics, 10 (2022), 2445. https://doi.org/10.3390/math10142445 doi: 10.3390/math10142445
[23]	J. Caceres, C. Hernado, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara, et al., On the metric dimension of cartesian products of graphs, SIAM J. Discrete Math., 21 (2007), 423–441. https://doi.org/10.1137/050641867 doi: 10.1137/050641867
[24]	B. Spinelli, L. E. Celis, P. Thiran, Observer placement for source localization: The effect of budgets and transmission variance, In: 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2016,743–751. https://doi.org/10.1109/ALLERTON.2016.7852307
[25]	B. Spinelli, L. E. Celis, P. Thiran, How many sensors to localize the source? The double metric dimension of random networks, In: 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2018, 1036–1043. https://doi.org/10.1109/ALLERTON.2018.8635897
[26]	J. Kratica, M. Cangalovic, V. Kovacevic-Vujcic, Computing minimal doubly resolving sets of graphs, Comput. Oper. Res., 36 (2009), 2149–2159. https://doi.org/10.1016/j.cor.2008.08.002 doi: 10.1016/j.cor.2008.08.002
[27]	M. Cangalovic, J. Kratica, V. Kovacevic-Vujcic, M. Stojanovic, Minimal doubly resolving sets of prism graphs, Optimization, 62 (2013), 1037–1043. https://doi.org/10.1080/02331934.2013.772999 doi: 10.1080/02331934.2013.772999
[28]	J. Kratica, V. Kovacevic-Vujcic, M. Cangalovic, M. Stojanovic, Minimal doubly resolving sets and the strong metric dimension of some convex polytope, 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
[29]	J. Kratica, V. Kovacevic-Vujcic, M. Cangalovic, M. Stojanovic, Minimal doubly resolving sets and the strong metric dimension of Hamming graphs, Appl. Anal. Discrete Math., 6 (2012), 63–71. https://doi.org/10.2298/AADM111116023K doi: 10.2298/AADM111116023K
[30]	X. Chen, X. Hu, C. Wang, Approximation for the minimum cost doubly resolving set problem, Theor. Comput. Sci., 609 (2016), 526–543. https://doi.org/10.1016/j.tcs.2015.03.048 doi: 10.1016/j.tcs.2015.03.048
[31]	A. Ahmad, S. Sultan, On minimal doubly resolving sets of circulant graphs, Acta Mech. Slovaca, 21 (2017), 6–11. https://doi.org/10.21496/ams.2017.002 doi: 10.21496/ams.2017.002
[32]	M. Ahmad, Z. Zahid, M. Javaid, M. A. Ashebo, A study on minimal doubly resolving sets of certain families of networks, IEEE Access, 11 (2023), 56344–56352. https://doi.org/10.1109/ACCESS.2023.3282701 doi: 10.1109/ACCESS.2023.3282701
[33]	A. Ahmad, M. Baca, S. Sultan, Minimal doubly resolving sets of necklace graph, Math. Rep., 20 (2018), 123–129.
[34]	M. Jannesari, Graphs with doubly resolving number 2, Discrete Appl. Math., 339 (2023), 178–183. https://doi.org/10.1016/j.dam.2023.06.017 doi: 10.1016/j.dam.2023.06.017
[35]	M. Ahmad, Z. Zahid, M. Javaid, E. Bonyah, Studies of chordal ring networks via double metric dimensions, Math. Probl. Eng., 2022 (2022), 8303242. https://doi.org/10.1155/2022/8303242 doi: 10.1155/2022/8303242
[36]	H. Raza, S. Hayat, X. F. Pan, On the fault-tolerant metric dimension of certain interconnection networks, J. Appl. Math. Comput., 60 (2019), 517–535. https://doi.org/10.1007/s12190-018-01225-y doi: 10.1007/s12190-018-01225-y
[37]	M. Ahmad, Z. Zahid, S. Zafar, On minimal edge version of doubly resolving sets of a graph, J. Comb. Math. Comb. Comput., 119 (2024), 175–184. https://doi.org/10.61091/jcmcc119-18 doi: 10.61091/jcmcc119-18
[38]	J. B. Liu, A. Zafari, Computing minimal doubly resolving sets and the strong metric dimension of the layer sun graph and the line graph of the layer sun graph, Complexity, 2020 (2020), 6267072. https://doi.org/10.1155/2020/6267072 doi: 10.1155/2020/6267072
[39]	M. Ahmad, Z. Zahid, T. Rashid, J. L. G. Guirao, Computing edge version of resolvability and double resolvability of a graph, J. Chem., 2022 (2022), 2448032. https://doi.org/10.1155/2022/2448032 doi: 10.1155/2022/2448032
[40]	J. B. Liu, A. Zafari, H. Zarei, Metric dimension, minimal doubly resolving sets, and the strong metric dimension for jellyfish graph and cocktail party graph, Complexity, 2020 (2020), 9407456. https://doi.org/10.1155/2020/9407456 doi: 10.1155/2020/9407456
[41]	J. B. Liu, Z. Zahid, R. Nasir, W. Nazeer, Edge version of metric dimension and doubly resolving sets of the necklace graphs, Mathematics, 6 (2018), 243. https://doi.org/10.3390/math6110243 doi: 10.3390/math6110243
[42]	M. Ahmad, N. Ameen, Z. Zahid, S. Zafar, Computing edge version of metric and double metric dimensions of Kayak paddle graphs, Discret. Math. Algorit., 12 (2020), 2050070. https://doi.org/10.1142/S1793830920500706 doi: 10.1142/S1793830920500706
[43]	J. Lv, X. Lv, R. Nasir, Z. Zahid, The edge version of metric dimension for the family of circulant graphs $C_n(1, 2)$, in IEEE Access, 9 (2021), 78165–78173. https://doi.org/10.1109/ACCESS.2021.3083182
[44]	B. Spinelli, L. Brunella, E. Celis, P. Thiran, The effect of transmission variance on observer placement for source-localization, Appl. Netw. Sci., 2 (2017), 20. https://doi.org/10.1007/s41109-017-0040-5 doi: 10.1007/s41109-017-0040-5

Reader Comments

Your name:*

Email:*
© 2024 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)