Solving Edges Deletion Problem of Complete Graphs - Anwar N. Jasim; Alaa A. Najim (مجلة بغداد للعلوم, 2024)
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 .