Por Damján Tárkány (Joint work with Luis Gouveia).

Perturbation i.e. addition or removal of edges alters the structure of a graph and can change the distance between nodes and the graph diameter. This can model the effect of line failures and repairs on delay in a communication network, for instance. We give an overview of known results about perturbations with maximal effect on the graph diameter. In particular, limits on the size and effect of such additions are presented and the computational complexity of finding such deletions is shown.