Rumor spreading via coupling
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.