Flooding time in edge-Markovian dynamic graphs

We introduce stochastic time-dependency in evolving graphs: starting from in arbitrary, initial edge probability distribution, at every time step! every edge changes it's state (existing or not) according to a two-state Markovian process with probabilities 1) (edge birth-rate) and q (edge death-rate). If all edge exists at time t then, at time t+1 it dies with probability q. If instead the edge does not exist at time 1, then it will come into existence at time t + 1 with Probability 1). Such evolving graph model is a. wide generalization of time-independent dynamic random graphs [6] and will be called edge-Markovian. dynamic graphs. We investigate the speed of information dissemination in such dynamic graphs. We provide nearly tight; bounds (which in fact turn out to be tight for a wide range of probabilities p and q) oil the completion Chile of the flooding mechanism aiming to broadcast a piece of information from a source node to all nodes. In particular, we provide: i) A tight characterization of the class of edge-Markovian dynamic graphs where flooding time is constant and. thus, it does not asymptotically depend oil the initial probability distribution. ii) A flight characterization of the class of edge-Markovian dynamic graphs where flooding time does not asymptotically depend oil the edge death-rate q.