Optimizing SNARK networks via double metric dimension

Muhammad Ahmad; Muhammad Faheem; Sanaa A. Bajri; Zohaib Zahid; Muhammad Javaid; Hamiden Abd El-Wahed Khalifa; Muhammad Ahmad; Muhammad Faheem; Sanaa A. Bajri; Zohaib Zahid; Muhammad Javaid; Hamiden Abd El-Wahed Khalifa

doi:10.3934/math.20241074

AIMS Mathematics

2024, Volume 9, Issue 8: 22091-22111. doi: 10.3934/math.20241074

Previous Article Next Article

Research article Special Issues

Optimizing SNARK networks via double metric dimension

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: 30 April 2024 Revised: 23 June 2024 Accepted: 01 July 2024 Published: 15 July 2024
MSC : 05C12

Doubly resolving sets (DRSs) provide a promising approach for source detection. They consist of minimal subsets of nodes with the smallest cardinality, referred to as the double metric dimension (DMD), that can uniquely identify the location of any other node within the network. Utilizing DRSs can improve the accuracy and efficiency of the identification of the origin of a diffusion process. This ability is crucial for early intervention and control in scenarios such as epidemic outbreaks, misinformation spreading in social media, and fault detection in communication networks. In this study, we computed the DMD of flower snarks $ J_{m} $ and quasi-flower snarks $ G_{m} $ by describing their minimal doubly resolving sets (MDRSs). We deduce that the DMD for the flower snarks $ J_{m} $ is finite and depends on the network's order, and the DMD for the quasi-flower snarks $ G_{m} $ is finite and independent of the network's order. Furthermore, our findings offer valuable insights into the structural features of complex networks. This knowledge can offer direction for future studies in network theory and its practical implementations.
- optimization,
- complex networks,
- metric dimension,
- doubly resolving sets,
- flower snarks,
- quasi-flower snarks
Citation: Muhammad Ahmad, Muhammad Faheem, Sanaa A. Bajri, Zohaib Zahid, Muhammad Javaid, Hamiden Abd El-Wahed Khalifa. Optimizing SNARK networks via double metric dimension[J]. AIMS Mathematics, 2024, 9(8): 22091-22111. doi: 10.3934/math.20241074

Related Papers:

Abstract

Doubly resolving sets (DRSs) provide a promising approach for source detection. They consist of minimal subsets of nodes with the smallest cardinality, referred to as the double metric dimension (DMD), that can uniquely identify the location of any other node within the network. Utilizing DRSs can improve the accuracy and efficiency of the identification of the origin of a diffusion process. This ability is crucial for early intervention and control in scenarios such as epidemic outbreaks, misinformation spreading in social media, and fault detection in communication networks. In this study, we computed the DMD of flower snarks $ J_{m} $ and quasi-flower snarks $ G_{m} $ by describing their minimal doubly resolving sets (MDRSs). We deduce that the DMD for the flower snarks $ J_{m} $ is finite and depends on the network's order, and the DMD for the quasi-flower snarks $ G_{m} $ is finite and independent of the network's order. Furthermore, our findings offer valuable insights into the structural features of complex networks. This knowledge can offer direction for future studies in network theory and its practical implementations.

References

[1]	P. J. Slater, Leaves of trees, In: Proceeding of the 6th southeastern conference on combinatorics, graph theory, and computing, congressus numerantium, 14 (1975), 549–559.
[2]	F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Comb., 2 (1976), 191–195.
[3]	Z. Beerliova, F. Eberhard, T. Erlabach, A. Hall, M. Hoffmann, M. Mihalak, et al., Network discovery and verification, IEEE J. Sel. Area. Comm., 24 (2006), 2168–2181. https://doi.org/10.1109/JSAC.2006.884015 doi: 10.1109/JSAC.2006.884015
[4]	K. Liu, N. Abu-Ghazaleh, Virtual coordinate with backtracking for void transversal in geographic routing, Berlin, Heidelberg: Springer, 2006, 46–59. https://doi.org/10.1007/11814764_6
[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
[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]	V. Chvtal, Mastermind, Combinatorica, 3 (1983), 325–329. https://doi.org/10.1007/BF02579188
[9]	P. Erdos, A. Renyi, On two problems of information theory, Publ. Math. Inst. Hung. Acad. Sci., 8 (1963), 241–254.
[10]	B. Lindstrom, On a combinatory detection problem I, Publ. Math. Institute Hung., 9 (1964), 195–207.
[11]	A. Ahmad, M. Baca, S. Sultan, Computing the metric dimension of kayak paddles graph and cycles with chord, Proyecciones, 39 (2020), 287–300. http://dx.doi.org/10.22199/issn.0717-6279-2020-02-0018 doi: 10.22199/issn.0717-6279-2020-02-0018
[12]	M. Ali, G. Ali, M. Imran, A. Q. Baig, M. K. Shafiq, On the metric dimension of Mobius ladders, Ars Comb., 105 (2012), 403–410.
[13]	R. F. Bailey, K. Meagher, On the metric dimension of Grassmann graphs, Discrete Math. Theoret. Comput. Sci., 13 (2011), 97–104. https://doi.org/10.46298/dmtcs.532 doi: 10.46298/dmtcs.532
[14]	R. F. Bailey, P. J. Cameron, Basie size, metric dimension and other invariants of groups and graphs, Bull. Lond. Math. Soc., 43 (2011), 209–242. https://doi.org/10.1112/blms/bdq096 doi: 10.1112/blms/bdq096
[15]	M. Fehr, S. Gosselin, O. R. Oellermann, The metric dimension of Cayley digraphs, Discrete Math., 306 (2006), 31–41. https://doi.org/10.1016/j.disc.2005.09.015 doi: 10.1016/j.disc.2005.09.015
[16]	A. Ahmad, M. Imran, O. Al-Mushayt, S. A. U. H. Bokhary, On the metric dimension of barycentric subdivision of Cayley graphs $Cay (Z_n \bigoplus Z_m)$, Miskolc Math. Notes, 16 (2015), 637–646. https://doi.org/10.18514/MMN.2015.1192 doi: 10.18514/MMN.2015.1192
[17]	T. Vetrik, A. Ahmad, Computing the metric dimension of the categorial product of some graphs, Int. J. Comput. Math., 94 (2017), 363–371. https://doi.org/10.1080/00207160.2015.1109081 doi: 10.1080/00207160.2015.1109081
[18]	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
[19]	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
[20]	M. Imran, H. M. A. Siddiqui, Computing the metric dimension of conves polytopes generated by the wheel related graphs, Acta Math. Hungar., 149 (2016), 10–30. https://doi.org/10.1007/s10474-016-0606-1 doi: 10.1007/s10474-016-0606-1
[21]	H. M. A. Siddiqui, M. Imran, Computing the metric dimension of wheel related graphs, Appl. Math. Comput., 242 (2014), 624–632. https://doi.org/10.1016/j.amc.2014.06.006 doi: 10.1016/j.amc.2014.06.006
[22]	R. Burdett, M. Haythorpe, A. Newcombe, Variants of the domination number for flower snarks, Ars Math. Contemp., 24 (2024), 1–26. https://doi.org/10.26493/1855-3974.2710.f3d doi: 10.26493/1855-3974.2710.f3d
[23]	M. M. Danas, The mixed metric dimension of flower snarks and wheels, Open Math., 19 (2021), 629–640. https://doi.org/10.1515/math-2021-0065 doi: 10.1515/math-2021-0065
[24]	A. Girisha, P. Rajendra, U. V. C. Kumar, S. Pushpa, On metric dimensions of flower graphs, J. Phys. Conf. Ser., 2571 (2023), 012019. https://doi.org/10.1088/1742-6596/2571/1/012019 doi: 10.1088/1742-6596/2571/1/012019
[25]	J. B. Liu, M. F. Nadeem, M. Azeem, Bounds on the partition dimension of convex polytopes, Comb. Chem. High Throughput Scr., 25 (2022), 547–553. https://doi.org/10.2174/1386207323666201204144422 doi: 10.2174/1386207323666201204144422
[26]	R. Nawaz, M. K. Jamil, M. Azeem, Edge-based metric resolvability of anti-depression molecular structures and its application, Results Chem., 7 (2024), 101458. https://doi.org/10.1016/j.rechem.2024.101458 doi: 10.1016/j.rechem.2024.101458
[27]	J. Caceres, C. Hernando, M. Mora, I. M. Pelayoe, M. L. Puertas, On the metric dimension of infinite graphs, Electron. Notes Discrete Math., 35 (2012), 15–20. https://doi.org/10.1016/j.endm.2009.11.004 doi: 10.1016/j.endm.2009.11.004
[28]	M. R. Garey, D. S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, 1 Eds., W. H. Freeman, 1979.
[29]	Z. Shao, S. M. Sheikholeslami, P. Wu, J. B. Liu, The metric dimension of some generalized Petersen graphs, Discrete Dyn. Nature Soc., 2018 (2018), 531958. https://doi.org/10.1155/2018/4531958 doi: 10.1155/2018/4531958
[30]	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
[31]	M. Baca, E. T. Baskoro, A. N. M. Salman, S. W. Saputro, D. Suprijanto, The metric dimension of regular bipartite graphs, Bull. Math. Soc. Sci. Math. Roumanie, 54 (2011), 15–28.
[32]	I. Tomescu, M. Imran, R-Sets and metric dimension of necklace graphs, Appl. Math. Inf. Sci., 9 (2015), 63–67. http://dx.doi.org/10.12785/amis/010109 doi: 10.12785/amis/010109
[33]	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
[34]	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
[35]	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
[36]	A. Ahmad, M. Baca, S. Sultan, Minimal doubly resolving sets of necklace graph, Math. Rep., 20 (2018), 123–129.
[37]	M. Ahmad, D. Alrowaili, R. Ali, Z. Zahid, I. Siddique, Double metric resolvability in convex polytopes, J. Math., 2022 (2022), 884924. https://doi.org/10.1155/2022/5884924 doi: 10.1155/2022/5884924
[38]	M. Ahmad, D. Alrowaili, Z. Zahid, I. Siddique, A. Iampan, Minimal doubly resolving sets of some classes of convex polytopes, J. Math., 2022 (2022), 1818734. https://doi.org/10.1155/2022/1818734 doi: 10.1155/2022/1818734
[39]	A. Ahmad, M. Baca, S. Sultan, On the minimal doubly resolving sets of Harary graph, Math. Univ. Comenian., 89 (2020), 123–129.
[40]	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.002. doi: 10.21496/ams.002
[41]	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
[42]	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
[43]	X. Chen, C. Wang, Approximability of the minimum weighted doubly resolving set problem, In: Lecture notes in computer science, Springer, 8591 (2014), 357–368. https://doi.org/10.1007/978-3-319-08783-2_31
[44]	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
[45]	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), 407456. https://doi.org/10.1155/2020/9407456 doi: 10.1155/2020/9407456
[46]	M. Ahmad, Z. Zahid, M. Javaid, E. Bonyah, Studies of chordal ring networks via double metric dimensions, Math. Probl. Eng., 2022 (2022), 303242. https://doi.org/10.1155/2022/8303242 doi: 10.1155/2022/8303242
[47]	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), 267072. https://doi.org/10.1155/2020/6267072 doi: 10.1155/2020/6267072
[48]	L. Pan, M. Ahmad, Z. Zahid, S. Zafar, Computation of the double metric dimension in convex polytopes, J. Math., 2021 (2021), 958969. https://doi.org/10.1155/2021/9958969 doi: 10.1155/2021/9958969
[49]	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
[50]	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
[51]	B. Spinelli, L. 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
[52]	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
[53]	M. Imran, S. A. H. Bokhary, A. Ahmad, A. Seminicova-Fenovcikova, On classes of regular graphs with constant metric dimension, Acta Math. Sci., 33 (2013), 187–206. https://doi.org/10.1016/S0252-9602(12)60204-5 doi: 10.1016/S0252-9602(12)60204-5
[54]	R. Naeem, M. Imran, Metric dimension and exchange property for resolving sets in rotationally-symmetric graphs, Appl. Math. Inf. Sci., 8 (2014), 1665–1674. https://doi.org/10.12785/amis/080422 doi: 10.12785/amis/080422

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)