Bounds on expected propagation time of probabilistic zero forcing

DOI10.1016/J.EJC.2021.103405MaRDI QIDQ1979443zbMATH OpenOpenAlexFDO

Authors Shyam Narayanan, Alec Sun

Publication date 2 September 2021

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

graph infection numberiterative coloring process on a graphMarkov chain

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Games involving graphs (91A43)

Abstract: Probabilistic zero forcing is a coloring game played on a graph where the goal is to color every vertex blue starting with an initial blue vertex set. As long as the graph is connected, if at least one vertex is blue then eventually all of the vertices will be colored blue. The most studied parameter in probabilistic zero forcing is the expected propagation time starting from a given vertex of $G.$ In this paper we improve on upper bounds for the expected propagation time by Geneson and Hogben and Chan et al. in terms of a graph's order and radius. In particular, for a connected graph $G$ of order $n$ and radius $r,$ we prove the bound $extept(G)=O(rlog(n/r)).$ We also show using Doob's Optional Stopping Theorem and a combinatorial object known as a cornerstone that $extept(G)len/2+O(logn).$ Finally, we derive an explicit lower bound $extept(G)gelo{g}_{2}lo{g}_{2}n.$

Recommendations

• Propagation time for probabilistic zero forcing
• Probabilistic Zero Forcing on Grid, Regular, and Hypercube Graphs
• Probabilistic zero forcing on random graphs
• Zero forcing propagation time on oriented graphs
• Using Markov chains to determine expected propagation time for probabilistic zero forcing

Cites work

• An upper bound for the minimum rank of a graph
• Fast-mixed searching and related problems on graphs
• Iteration index of a zero forcing set in a graph
• Nondiscriminatory propagation on trees
• On minimum rank and zero forcing sets of a graph
• Probabilistic zero forcing on random graphs
• Probability and random processes.
• Probalistic zero forcing in graphs
• Propagation time for zero forcing on a graph
• Randomized rumor spreading in poorly connected small-world networks
• Robustness of randomized rumour spreading
• Throttling zero forcing propagation speed on graphs
• Using Markov chains to determine expected propagation time for probabilistic zero forcing
• Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph
• Zero forcing and power domination for graph products
• Zero forcing parameters and minimum rank problems

Cited in

(6)

• Tight bounds on probabilistic zero forcing on hypercubes and grids
• Upper bounds for positive semidefinite propagation time
• Probabilistic zero forcing on random graphs
• Using Markov chains to determine expected propagation time for probabilistic zero forcing
• Propagation time for probabilistic zero forcing
• Zero forcing with random sets

This page was built for publication: Bounds on expected propagation time of probabilistic zero forcing

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