Probabilistic variations of zero forcing and power domination

Abstract

Zero forcing is a graph propagation process in which white vertices are colored blue by neighboring blue vertices. Probabilistic zero forcing is a generalization of zero forcing where a blue vertex $v$ colors a white neighbor blue with probability proportional to the number of blue neighbors of $v$. In this dissertation we introduce two probabilistic variations on zero forcing and probabilistic zero forcing with connections to disease spread and power grid modeling.

The first variation is reversion probabilistic zero forcing (RPZF), which generalizes probabilistic zero forcing so that blue vertices now "recover" (revert to being white) at some fixed rate. We formalize the study of RPZF through Markov chain theory, which provides methods of calculating any graph's probability of becoming all white or all blue from a given starting configuration as well as the time at which this is expected to occur. Moreover, the long-term behavior of the process is studied in-depth on the complete graph and some related structures, developing a threshold number of blue vertices such that with high probability the graph is entirely blue in the next round.

The second variation is fragile power domination. The power domination problem seeks to minimize the number of phasor measurement units (PMUs) necessary to monitor the power grid. This is formalized in a graph theoretic process consisting of a domination step (sensors observe neighboring vertices) and a zero forcing step (observation propagates throughout the graph according to the zero forcing rule). Fragile power domination introduces random sensor failure before the domination step, and the goal of fragile power domination is to understand optimal sensor placements under different probabilities of sensor failure. In particular, we study the expected number of observed vertices and relate this to fault-tolerant and PMU-defect-robust power domination.