Robustness of the Rotor-router Mechanism

We consider the model of exploration of an undirected graph

G

by a single

agent

which is called the

rotor-router mechanism

or the

Propp machine

(among other names). Let

π

v

indicate the edge adjacent to a node

v

which the agent took on its last exit from

v

. The next time when the agent enters node

v

, first a “rotor” at node

v

advances pointer

π

v

to the edge

${\it next}(\pi_v)$

which is next after the edge

π

v

in a fixed cyclic order of the edges adjacent to

v

. Then the agent is directed onto edge

π

v

to move to the next node. It was shown before that after initial

O

(

mD

) steps, the agent periodically follows one established Eulerian cycle, that is, in each period of 2

m

consecutive steps the agent traverses each edge exactly twice, once in each direction. The parameters

m

and

D

are the number of edges in

G

and the diameter of

G

. We investigate robustness of such exploration in presence of faults in the pointers

π

v

or dynamic changes in the graph. We show that after the exploration establishes an Eulerian cycle,

if at some step the values of

k

pointers

π

v

are arbitrarily changed, then a new Eulerian cycle is established within

O

(

km

) steps;

if at some step

k

edges are added to the graph, then a new Eulerian cycle is established within

O

(

km

) steps;

if at some step an edge is deleted from the graph, then a new Eulerian cycle is established within

O

(

γm

) steps, where

γ

is the smallest number of edges in a cycle in graph

G

containing the deleted edge.

Our proofs are based on the relation between Eulerian cycles and spanning trees known as the “BEST” Theorem (after de

B

ruijn, van Aardenne-

E

hrenfest,

S

mith and

T

utte).