Propagation time for probabilistic zero forcing Geneson, Jesse Hogben, Leslie Hogben, Leslie
dc.contributor.department Mathematics 2021-07-07T22:18:33.000 2021-08-14T19:03:45Z 2021-08-14T19:03:45Z Mon Jan 01 00:00:00 UTC 2018 2018-01-01
dc.description.abstract <p>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.</p>
dc.description.comments <p>This is a pre-print of the article Geneson, Jesse, and Leslie Hogben. "Propagation time for probabilistic zero forcing." <em>arXiv preprint arXiv:1812.10476</em> (2018). Posted with permission.</p>
dc.format.mimetype application/pdf
dc.identifier archive/
dc.identifier.articleid 1281
dc.identifier.contextkey 23712786
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath math_pubs/272
dc.language.iso en
dc.source.bitstream archive/|||Fri Jan 14 23:06:47 UTC 2022
dc.subject.disciplines Discrete Mathematics and Combinatorics
dc.subject.keywords probabilistic zero forcing
dc.subject.keywords expected propagation time
dc.subject.keywords ℓ-round probability
dc.subject.keywords confidence propagation
dc.subject.keywords throttling
dc.title Propagation time for probabilistic zero forcing
dc.type article
dc.type.genre article
dspace.entity.type Publication
relation.isAuthorOfPublication 0131698a-00df-41ad-8919-35fb630b282b
relation.isOrgUnitOfPublication 82295b2b-0f85-4929-9659-075c93e82c48
Original bundle
Now showing 1 - 1 of 1
397.61 KB
Adobe Portable Document Format