Propagation processes on graphs and applications
Date
2022-08
Authors
Conrad, Esther Dawn
Major Professor
Advisor
Hogben, Leslie
Rozier, Kristin Y
Newman, Jennifer
Ciardo, Gianfranco
Young, Michael
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Abstract
Graph propagation processes are modeling tools. We begin with a graph G with vertices colored blue and white. At each step, we follow a rule to color the neighbors of blue vertices. And then we measure different phenomena. What is the least number of vertices necessary to color the whole graph blue? How long does it take to color the whole graph blue? Can these be balanced?
The first propagation process that we study models how sensors called phasor measurement units (PMUs) monitor an electrical power network. The power domination problem seeks to find the minimum number of PMUs needed. We study a variation of the power domination problem called the PMU-defect robust power domination problem. This seeks to minimize the number of PMUs needed given that k fail. We give a solution to the k-robust power domination problem for trees.
The second propagation process that we study provides an upper bound for the maximum nullity of a positive semidefinite graph, which is the maximum nullity over all symmetric positive semidefinite matrices whose non-zero off-diagonal entries correspond to the edges of the graph. Product throttling for positive semidefinite zero forcing answers the question of minimizing the product of the initial set of blue vertices needed, and the time it takes for all the vertices in the graph to turn blue. We give various results and bounds on the initial cost product throttling number, including a lower bound of 1+rad(G) and the initial cost product throttling number of a cycle.
The previous two propagation process follow a deterministic rule to change the white vertices of a graph to blue. Probabilistic zero forcing colors the neighbors of the blue vertices with a probabilistic function. Expected propagation time is the minimum expected time it takes for a graph to turn blue. We extend the definition of probabilistic zero forcing and expected propagation time to digraphs. We present examples of how to use a Markov matrix to find the expected propagation time for any digraph, and give a construction for the Markov matrix of a total order tournament. We also present an asymptotic bound for the expected propagation time of digraphs.
Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
dissertation