A Proposed Method by Using the Adjacency Matrix to Solve the Edges Deletion Problem of Complete Graphs
DOI:
https://doi.org/10.31642/JoKMC/2018/120101Keywords:
Edges deletion problem, Maximum diameter, Complete graph, Adjacency matrix .Abstract
Graph theory approaches can be used to investigate a network’s dependability and effectiveness, and the network’s connectivity can be used to assess its dependability. The efficiency of a network is measured by its diameter, which can be somewhat increased by removing some vertices or edges. In this work, the maximum diameter fn(tt) of the modified graph G with n (n≥4) vertices, which resulted from removing t edges from the complete graph Kn ,(n≥4) was determined using the adjacency matrix adj(Kn).
Downloads
References
[1] H.R. Hashim, F. Luca, H.B. Shelash and A.A. Shukur, “Generalized Lucas graphs,” Afrika Matematika: Springer, vol. 34, no.1,p10, 2023, https://doi.org/10.1007/s13370-023-01048-6. DOI: https://doi.org/10.1007/s13370-023-01048-6
[2] F. Werner,” Graph-theoretic problems and their new applications. Mathematics,” MDPI ,vol.8, no.3,p 445, 2020, https://doi.org/10.3390/books978-3-03928-799-4 . DOI: https://doi.org/10.3390/math8030445
[3] J. L Kalb and D. S Lee, “Network topology analysis”, Technical report, Sandia National Laboratories (SNL), Albuquerque, NM, and Livermore, CA (United States), 2008.
[4] V. Mohammadi, A. M. Rahmani, A. Darwesh and A. Sahafi, “Fault tolerance in fog-based Social Internet of Things,” Knowledge-Based Systems, vol. 265,pp110-376, 2023, https://doi.org/10.1016/j.knosys.2023.110376. DOI: https://doi.org/10.1016/j.knosys.2023.110376
[5] Y. Zou, L. Yang, G. Jing, R. Zhang and Z. Xie, “A sur vey of fault tolerant consensus in wireless networks,” High-Confidence Compu., 2024, https://doi.org/10.1016/j.hcc.2024.100202. DOI: https://doi.org/10.1016/j.hcc.2024.100202
[6] M.F. Nadeem, M. Imran, S. Afzal, M. Hafiz and Azeem, “Fault tolerance designs of interconnection networks, Peer-to-peer networking and applications,” Springer, vol.16, no.2, pp1125-1134, 2023, https://doi.org/10.1007/s12083-023-01462-4 . DOI: https://doi.org/10.1007/s12083-023-01462-4
[7] A.M. Rappoport and I.I. Kurochkin, “The graph diameter of a distributed system with a given dominant set,” 9th International Conference” Distributed Computing and Grid Technologies in Sci and Edu”(GRID 2021) Dubna, Russia,5-9, 2021, https://doi.org/10.54546/MLIT.2021.63.14.001. DOI: https://doi.org/10.54546/MLIT.2021.63.14.001
[8] N. Graham and F. Harary,” Changing and unchanging the diameter of a hypercube,” Discrete Applied Mathematics, vol. 37, pp265-274, 1992, https://doi.org/10.1016/0166 218X(92)90137-Y. DOI: https://doi.org/10.1016/0166-218X(92)90137-Y
[9] A. Bouabdallah, C. Delorme, and S. Djelloul, “Edge deletion preserving the diameter of the hypercube,” Discrete Applied Math., vol. 63, no. 1, pp 91-95, 1995, https://doi.org/10.1016/0166-218X(95)00023-K. DOI: https://doi.org/10.1016/0166-218X(95)00023-K
[10] A.A. Schoone, H.L. Bodlaender and L.J. Van, “Diameter increase caused by edge deletion,” Journal of graph theory, vol.11, no.3 ,pp409-427, 1987, https://doi.org/10.1002/jgt.3190110315. DOI: https://doi.org/10.1002/jgt.3190110315
[11] A.A. Najim and J. Xu , “Edge addition and edge deletion of graphs,” J. Univ. Sci. Technol. China, vol.36, no.3, pp254-257, 2006.
[12] A.N. Jasim and A.A. Najim, “Edges deletion problem of hypercube graphs for some n,” Discrete Mathematics, Algorithms and Applications,2024,https://doi.org/10.1142/S1793830924500459. DOI: https://doi.org/10.1142/S1793830924500459
[13] A.N. Jasim and A.A. Najim, “Solving Edges Deletion Problem of Generalized Petersen Graphs,” Journal of Kufa for Mathematics and Computer, vol.11, no.1, pp 6-10, 2024, http://dx.doi.org/10.31642/JoKMC/2018/110102. DOI: https://doi.org/10.31642/JoKMC/2018/110102
[14] A.N. Jasim and A.A. Najim, “Solving Edges Deletion Problem of Complete Graphs,” Baghdad Science Journal, vol.21, no.12, pp 4073-4082, 2024 https://doi.org/10.21123/bsj.2024.10128. DOI: https://doi.org/10.21123/bsj.2024.10128
[15] E.J. Kim, M. Milanic , J. Monnot and C. Picouleau, “Complexity and algorithms for constant diameter augmentation problems,” Theoretical Computer Science, vol. 904, pp 15-26, 2022, https://doi.org/10.1016/j.tcs.2021.05.020. DOI: https://doi.org/10.1016/j.tcs.2021.05.020
[16] M. Ju, J. Wang and S. Chang, “Diameter variability of hypercubes,” Theoretical Computer Science, vol. 542, pp 63-70, 2014, https://doi.org/10.1016/j.tcs.2014.04.033. DOI: https://doi.org/10.1016/j.tcs.2014.04.033
[17] S. F Florkowski, “Spectral graph theory of the hypercube”, Ph.D. thesis, Monterey, California. Naval Postgraduate School, https://hdl.handle.net/10945/3852, 2008.
Downloads
Published
Issue
Section
Categories
License
Copyright (c) 2025 Anwar Nasif Jasim
This work is licensed under a Creative Commons Attribution 4.0 International License.
which allows users to copy, create extracts, abstracts, and new works from the Article, alter and revise the Article, and make commercial use of the Article (including reuse and/or resale of the Article by commercial entities), provided the user gives appropriate credit (with a link to the formal publication through the relevant DOI), provides a link to the license, indicates if changes were made and the licensor is not represented as endorsing the use made of the work.
How to Cite
