Ricerc@Sapienza

We study the PUSH rumor spreading process in randomly evolving graphs. In par- ticular we focus on the so called edge-Markovian random graph model, where birth and death rates for the edges in the graph are investigated in various ranges of con- crete interest. We prove that the completion time of PUSH is O(log n) also for highly unbalanced rates that make the network disconnected at each time-step. Central to our result is the notion that we introduce of partial ordering, which, where preserved, allows to obtain bounds linking the model to simpler counterparts with independent link evolution.