Probalistic zero forcing in graphs

MaRDI QIDQ4925703zbMATH OpenFDO

Authors Cong X. Kang, Eunjeong Yi

Publication date 12 June 2013

Full work available at URL https://arxiv.org/abs/1204.6237

zbMATH Keywords

absorbing chainsMarkov processprobalistic color change ruleprobalistic zero forcingzero forcing

Mathematics Subject Classification ID

Trees (05C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: The emph{zero forcing number} $Z(G)$ of a graph $G$ is the minimum cardinality of a set $S$ of black vertices (whereas vertices in $V(G)setminusS$ are colored white) such that $V(G)$ is turned black after finitely many applications of "the (classical) color change rule": a white vertex is converted to a black vertex if it is the only white neighbor of a black vertex. Zero forcing number was introduced and used to bound the minimum rank of graphs by the "AIM Minimum Rank - Special Graphs Work Group". We introduce here a probabilistic color change rule (pccr) which is a natural generalization of the classical color change rule. We introduce a theory of probabilistic zero forcing arising out of the pccr; the theory yields a quantity $P_A(G)$, which can be viewed as the probability that a graph $G$ with an initial black set $A$ will be converted entirely to the color black. We also interpret the evolution of the sample spaces of this theory as a Markov process. We end with a few basic examples illustrating this theory.

Recommendations

• Probabilistic zero forcing on random graphs
• The zero forcing polynomial of a graph
• Propagation time for probabilistic zero forcing
• Using Markov chains to determine expected propagation time for probabilistic zero forcing
• Tight bounds on probabilistic zero forcing on hypercubes and grids

Cited in

(20)

• Infection in hypergraphs
• The zero forcing polynomial of a graph
• Effects of vertex degrees on the zero-forcing number and propagation time of a graph
• Bounds on expected propagation time of probabilistic zero forcing
• Logic circuits from zero forcing
• Tight bounds on probabilistic zero forcing on hypercubes and grids
• Blocking zero forcing processes in Cartesian products of graphs
• Probabilistic zero forcing on random graphs
• Zero-forcing in random regular graphs
• Properties of a \(q\)-analogue of zero forcing
• Three-state zero forcing on graphs
• Iteration index of a zero forcing set in a graph
• Fractional zero forcing via three-color forcing games
• Using Markov chains to determine expected propagation time for probabilistic zero forcing
• Probabilistic Zero Forcing on Grid, Regular, and Hypercube Graphs
• Propagation time for probabilistic zero forcing
• Zero forcing with random sets
• Probabilistic zero forcing with vertex reversion
• Exploring the influence of graph operations on zero forcing sets
• Throttling for metric dimension and its variants

This page was built for publication: Probalistic zero forcing in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4925703)