Propagation time for probabilistic zero forcing
From MaRDI portal
Abstract: Zero forcing is a coloring game played on a graph that was introduced more than ten years ago in several different applications. The goal is to color all the vertices blue by repeated use of a (deterministic) color change rule. Probabilistic zero forcing was introduced by Kang and Yi in [Probabilistic zero forcing in graphs, Bull. Inst. Combin. Appl. 67 (2013), 9--16] and yields a discrete dynamical system, which is a better model for some applications. 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 a natural parameter to study. We determine expected propagation time exactly for paths and cycles, establish the asymptotic value for stars, and present asymptotic upper and lower bounds for any graph in terms of its radius and order. We apply these results to obtain values and bounds on -round probabilistic zero forcing, throttling number for probabilistic zero forcing, and confidence levels for propagation time.
Recommendations
- Bounds on expected propagation time of probabilistic zero forcing
- Using Markov chains to determine expected propagation time for probabilistic zero forcing
- Propagation time for zero forcing on a graph
- Zero forcing propagation time on oriented graphs
- Positive semidefinite propagation time
- Expected coalescence time for a nonuniform allocation process
- Arrival times in a zero-range process with injection and decay
- Probabilistic zero forcing on random graphs
- Probabilistic Analysis of Rumor-Spreading Time
- On the error of \textit{a priori} sampling: zero forcing sets and propagation time
Cites work
- A lower bound on the zero forcing number
- A protocol for cooling and controlling composite systems by local interactions
- Bounds for the Zero Forcing Number of Graphs with Large Girth
- Bounds on expected propagation time of probabilistic zero forcing
- Domination in graphs with bounded propagation: Algorithms, formulations and hardness results
- Fast-mixed searching and related problems on graphs
- Inverse Problems and Zero Forcing for Graphs
- Iteration index of a zero forcing set in a graph
- On the runtime and robustness of randomized broadcasting
- Positive semidefinite propagation time
- Probabilistic zero forcing on random graphs
- Probalistic zero forcing in graphs
- Propagation time for zero forcing on a graph
- Randomized rumour spreading: the effect of the network topology
- The shortest-path problem for graphs with random arc-lengths
- The Zero Forcing Number of Graphs
- Throttling for the game of cops and robbers on graphs
- Throttling zero forcing propagation speed on graphs
- Upper bounds on the \(k\)-forcing number of a graph
- Using Markov chains to determine expected propagation time for probabilistic zero forcing
- Zero forcing and power domination for graph products
- Zero forcing parameters and minimum rank problems
- Zero forcing sets and the minimum rank of graphs
Cited in
(11)- Bounds on expected propagation time of probabilistic zero forcing
- Tight bounds on probabilistic zero forcing on hypercubes and grids
- On the zero forcing number and propagation time of oriented graphs
- Probabilistic zero forcing on random graphs
- Using Markov chains to determine expected propagation time for probabilistic zero forcing
- Propagation time for zero forcing on a graph
- Probalistic zero forcing in graphs
- Zero forcing propagation time on oriented graphs
- Zero forcing with random sets
- Probabilistic zero forcing with vertex reversion
- Throttling for metric dimension and its variants
This page was built for publication: Propagation time for probabilistic zero forcing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090539)
