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.