Journal of Graph Theory · 1987 · 102 citations · 4 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsGeometryGeometric GraphsGraph AlgorithmsGraph TheoryNetwork DiameterApproximate DiameterComputational Complexity Of Graph AlgorithmsDirected GraphsEdge-diameterGraph DiameterLower Bounds On DiameterUpper Bounds On Diameter
Abstract We consider the following problem: Given positive integers k and D , what is the maximum diameter of the graph obtained by deleting k edges from a graph G with diameter D , assuming that the resulting graph is still connected? For undirected graphs G we prove an upper bound of ( k + 1) D and a lower bound of ( k + 1) D − k for even D and of ( k + 1) D − 2 k + 2 for odd D ⩾ 3. For the special cases of k = 2 and k = 3, we derive the exact bounds of 3 D − 1 and 4 D − 2, respectively. For D = 2 we prove exact bounds of k + 2 and k + 3, for k ⩽ 4 and k = 6, and k = 5 and k ⩾ 7, respectively. For the special case of D = 1 we derive an exact bound on the resulting maximum diameter of order θ(√ k ). For directed graphs G , the bounds depend strongly on D : for D = 1 and D = 2 we derive exact bounds of θ(√ k ) and of 2 k + 2, respectively, while for D ⩾ 3 the resulting diameter is in general unbounded in terms of k and D . Finally, we prove several related problems NP‐complete.
4
THE MAXIMUM CONNECTIVITY OF A GRAPH
Frank Harary · Proceedings of the National Academy of Sciences · 1962 · 331 citations
Diameter bounds for altered graphs
Fan Chung, M. R. Garey · Journal of Graph Theory · 1984 · 85 citations
The complexity of designing a network with minimum diameter
Networks · 1981 · 57 citations
Computing, Computer Science, Design +14
Diameter vulnerability of graphs
Claudine Peyrat · Discrete Applied Mathematics · 1984 · 20 citations