The impact of dynamic events on the number of errors in networks

In order to achieve routing in a graph, nodes need to store routing information. In the case of shortest path routing, for a given destination, every node has to store an advice that is an outgoing link toward a neighbor. If this neighbor does not belong to a shortest path then the advice is considered as an error and the node giving this advice will be qualified a liar. This article focuses on the impact of graph dynamics on the advice set for a given destination. More precisely we show that, for a weighted graph G of diameter D with n nodes and m edges, the expected number of errors after M edge deletions is bounded by O(n(dot operator)M(dot operator)D/m). We also show that this bound is tight when M=O(n). Moreover, for M' node deletions, the expected number of errors is O(M'(dot operator)D). Finally we show that after a single edge addition the expected number of liars can be ?(n) for some families of graphs.