Solving Edges Deletion Problem of Complete Graphs
DOI:
https://doi.org/10.21123/bsj.2024.10128Keywords:
Altered graph, Complete graph, Diameter, Edges deletion problem, Graph theoryAbstract
As the network size increases, there is an increased probability that some components will fail. It is therefore necessary for the network to be able to maintain the interconnection even in the presence of faulty components. The likelihood of a failure in the connections between stations is higher than that of a failure in the stations themselves because of the nature of many networks. Numerous graph-theoretic methods can be used to examine the reliability and efficacy of a network, and the network's dependability is determined by its connectivity. For a parallel and distributed system, the maximum connection time between any two nodes in the network can be determined using the diameter of the graph. Diameter is often used to measure the efficiency of a network with the maximum delay or signal degradation. The diameter of a graph can be altered by adding or removing edges. In this paper, it has been considered how the diameter will increase after deleting the number of edges from the complete graph and calculating the maximum diameter. The maximum diameter of a connected graph with vertices is obtained after removing edges from a connected graph . The maximum diameter of a connected graph is derived from .
Received 08/11/2023
Revised 18/02/2024
Accepted 20/02/2024
Published Online First 20/06/2024
References
Saibavani TNP, Parvathi N. Power Domination in Different Graphs with Applications. Math Model Eng Probl. 2023; 10(2): 546-550. https://doi.org/10.18280/mmep.100222.
Al-Jarah R, Kashmola MY. Modeling the Power Grid Network of Iraq. Baghdad Sci J. 2023; 20(3): 879-892. https://doi.org/10.21123/bsj.2022.6959.
Revathy AS, Nair RR, Chithra MR. A Survey on-How the Diameter of a Graph is Affected by the Removal and the Addition of Edges. Int J Appl Eng Res. 2015; 10(16): 36169–36174.
Ekinci GB, Gauci JB. The Diameter Vulnerability of the Generalized Petersen Graph {GP [tk,k]}. Turk J Math. 2018; 42(6): 2897–2915. https://doi.org/10.3906/MAT-1802-66.
Abdul-Ghani SA, Abdul-Wahhab RD, Abood EW. Securing Text Messages Using Graph Theory and Steganography. Baghdad Sci J. 2022; 19(1): 189-196. http://dx.doi.org/10.21123/bsj.2022.19.1.0189.
Schoone AA, Bodlaende HLF, Van Leeuwen J. Diameter Increase Caused by Edge Deletion. J Graph Theory. 1987; 11(3): 409–427. https://doi.org/10.1002/jgt.3190110315.
Rappoport AM, Kurochkin II. 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 July 2021; 246–250.
Yannakakis M. Edge-Deletion Problems. SIAM J Comput. 1981; 10(2). https://doi.org/10.1137/0210021.
Chen LH, Hung LJ, Lotze H, Rossmanith P. Online Node- and Edge-Deletion Problems with Advice. Algorithmica 2021; 83. 2719–2753. https://doi.org/10.1007/s00453- 021-00840-9.
Chung FRK, Garey MR. Diameter Bounds for Altered Graphs. J Graph Theory. 1984; 8: 511–534.
Kim EJ, Milanič M, Monnot J, Picouleau C. Complexity and Algorithms for Constant Diameter Augmentation Problems. Theor Comput Sci. 15 February 2022; 904: 15 – 26. https://doi.org/10.1016/j.tcs.2021.05.020.
Swart CS. Distance Measures in Graphs and Subgraphs. Durban: University of Natal; 1996.
Alochukwu A, Dankelmann P. Edge-Fault Diameter of C_4-Free Graphs. Discrete Math. January 2024; 347(1). https://doi.org/10.1016/j.disc.2023.113678
Bouabdallah A, Delorme C, Djelloul S. Edge Deletion Preserving the Diameter of the Hypercube. Discrete Appl Math. 27 October 1995; 63(1): 91 – 95. https://doi.org/10.1016/0166-218X(95)00023-K.
Wang J-J, Ho T-Y, Ferrero D, Sung T-Y. Diameter Variability of Cycles and Tori. Inf Sci. 15 July 2008; 178(14): 2960–2967. https://doi.org/10.1016/j.ins.2008.03.008.
Fundikwa BT, Mazorodze JP, Mukwembi S. An Upper Bound on the Diameter of a 3-Edge-Connected C4-Free Graph. Indian J Pure Appl Math. 2020; 51: 1931–1938. https://doi.org/10.1007/s13226-020-0505-6.
Najim AA, Xu JM. Edge Addition and Edge Deletion of Graphs. J Univ Sci Technol China. 2006; 36(3): 254-257.
Swadi SA, Najim AA, Swadi KA. Some Exact Values for p (t, d). J Discret Math Sci Cryptogr. 2020; 23(7): 1399 – 1407. https://doi.org/10.1080/09720529.2020.1714889.
Abu-Khzam FN, Makarem N, Shehab M. An Improved Fixed-Parameter Algorithm for 2-Club Cluster Edge Deletion. Theor Comput Sci. 22 May 2023; 958: 113864. https://doi.org/10.1016/j.tcs.2023.113864.
Xu J. Topological Structure and Analysis of Interconnection Networks. Network Theory and Applications (NETA, volume 7). New York: Springer; 2001. 342 p. https://doi.org/10.1007/978-1-4757-3387-7.
Downloads
Issue
Section
License
Copyright (c) 2024 Anwar N. Jasim , Alaa A. Najim
This work is licensed under a Creative Commons Attribution 4.0 International License.
How to Cite
