Premium
Diameter increase caused by edge deletion
Author(s) -
Schoone A. A.,
Bodlaender H. L.,
Van Leeuwen J.
Publication year - 1987
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190110315
Subject(s) - combinatorics , mathematics , upper and lower bounds , graph , order (exchange) , undirected graph , discrete mathematics , mathematical analysis , finance , economics
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.