Using Markov chains to determine expected propagation time for probabilistic zero forcing

MaRDI QIDQ3299342zbMATH OpenFDO

Authors Yu Chan, Emelie Curl, Kevin F. R. Liu, Isaac Odegard, Michael S. Ross, Jesse Geneson, Leslie Hogben

Publication date 22 July 2020

Full work available at URL https://arxiv.org/abs/1906.11083, https://journals.uwyo.edu/index.php/ela/article/view/5127

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Markov chainexpected propagation timeprobabilistic zero forcing

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Positive matrices and their generalizations; cones of matrices (15B48) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Stochastic matrices (15B51) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: 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 studied. Given a Markov transition matrix for a probabilistic zero forcing process, we establish an exact formula for expected propagation time. We apply Markov chains to determine bounds on expected propagation time for various families of graphs.

Recommendations

• Propagation time for probabilistic zero forcing
• Probabilistic Zero Forcing on Grid, Regular, and Hypercube Graphs
• Bounds on expected propagation time of probabilistic zero forcing
• Probabilistic zero forcing on random graphs
• Propagation time for zero forcing on a graph

Cites work

• scientific article; zbMATH DE number 6125590 (Why is no real title available?)
• A protocol for cooling and controlling composite systems by local interactions
• Fast-mixed searching and related problems on graphs
• Graph theory
• Iteration index of a zero forcing set in a graph
• Positive semidefinite propagation time
• Probalistic zero forcing in graphs
• Propagation time for zero forcing on a graph
• The minimum rank of symmetric matrices described by a graph: a survey
• Throttling zero forcing propagation speed on graphs
• Zero forcing and power domination for graph products
• Zero forcing sets and the minimum rank of graphs

Cited in

(6)

• Propagation time for probabilistic zero forcing
• Zero forcing with random sets
• Bounds on expected propagation time of probabilistic zero forcing
• Probabilistic zero forcing on random graphs
• Tight bounds on probabilistic zero forcing on hypercubes and grids
• Probalistic zero forcing in graphs

This page was built for publication: Using Markov chains to determine expected 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 Q3299342)