Using Markov Chains to Determine Expected Propagation Time for Probabilistic Zero Forcing
2020
Zero forcing is a coloring game played on a graph where each vertex is initially colored blue or white and the goal is to color all the vertices blue by repeated use of a (deterministic) color change rule starting with as few blue vertices as possible. Probabilistic zero forcing yields a discrete dynamical system governed by a Markov chain. Since in a connected graph any one vertex can eventually color the entire graph blue using probabilistic zero forcing, the expected time to do this is studied. Given a Markov transition matrix for a probabilistic zero forcing process, an exact formula is established for expected propagation time. Markov chains are applied to determine bounds on expected propagation time for various families of graphs.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
7
Citations
NaN
KQI