The impact of edge deletions on the number of errors in networks
Christian Glacet

In order to achieve routing in a graph, nodes need to store routing information. In the case of shortest path routing, every node has to store an outgoing link that is closer to a given destination. This presentation focuses on the impact of graph dynamics on these pieces of information. More precisely I'll show that, for a graph G of diameter D with n nodes and m edges, the expected number of errors after X edge deletions is bounded by O(n X D/m). I will also show that this bound is tight when D = o(n). Finally I'll show that after a single edge addition the expected number of liars can be Θ(n) for some families of graphs.