Expected propagation time for probabilistic zero forcing

Thumbnail Image
Date
2022-06
Authors
Geneson, Jesse
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
The University of Queensland on behalf of the Combinatorial Mathematics Society of Australasia
Abstract
Zero forcing is a coloring process on a graph that was introduced more than fifteen 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 [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 and confidence levels for propagation time.
Series Number
Journal Issue
Is Version Of
Versions
Article
Propagation time for probabilistic zero forcing
( 2018-01-01) Geneson, Jesse ; Hogben, Leslie ; Department of Mathematics

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.

Series
Academic or Administrative Unit
Type
article
Comments
This article is published as Geneson, Jesse, and Leslie Hogben. "Expected propagation time for probabilistic zero forcing." Australasian Journal of Combinatorics 83 (2022): 397.
Rights Statement
Copyright The author(s). Released under the CC BY-ND 4.0 International License
Copyright
Funding
DOI
Supplemental Resources
Source
Collections