東華大學圖書館 |

Propagation Processes: Full Throttling and Probabilistic Zero Forcing.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Propagation Processes: Full Throttling and Probabilistic Zero Forcing./
Author:	Ross, Michael Steven.
Published:	Ann Arbor : ProQuest Dissertations & Theses, : 2022,
Description:	54 p.
Notes:	Source: Dissertations Abstracts International, Volume: 83-12, Section: B.
Contained By:	Dissertations Abstracts International83-12B.
Subject:	Mathematics. -
ISBN:	9798819384749

Propagation Processes: Full Throttling and Probabilistic Zero Forcing.
Ross, Michael Steven.

Propagation Processes: Full Throttling and Probabilistic Zero Forcing. - Ann Arbor : ProQuest Dissertations & Theses, 2022 - 54 p.

Source: Dissertations Abstracts International, Volume: 83-12, Section: B.

Thesis (Ph.D.)--Iowa State University, 2022.

This item must not be sold to any third party vendors.

Zero forcing is a process that arose in many contexts, including mathematical physics under the name ``graph infection", in graph searching problems in computer science, and in linear algebra as an upper bound on the multiplicity of an eigenvalue of a matrix described by a graph. With standard zero forcing, one colors some initial vertices of a graph blue, and whenever a vertex is the only white neighbor of a blue vertex, it is also colored blue. The diverse origins of zero forcing have inspired many variants of this color change rule. From its linear algebra aspect comes positive semidefinite zero forcing, where in each time step one first splits the graph obtained by deleting the blue vertices across its connected components and then does the standard zero forcing rule on the induced subgraph on the vertices of each component together with the blue vertices of the graph. On the graph searching side, the game of cops and robbers and its variants have many similar properties, and standard zero forcing is equivalent to fast mixed graph searching. In each case there are a few core aspects that are studied for a given graph: the number of initial vertices required to complete the process, the amount of time required for the process to complete given a specific set of starting vertices, and ``throttling" parameters that seek to minimize some combination of the two (typically the sum).Building on the behavior that positive semidefinite zero forcing exhibits on trees, we introduce full forcing, where blue vertices will force every neighbor they have every round. Trivially, any single vertex in a connected graph is a full forcing set, and the minimum propagation time across singleton sets is just the radius of the graph; thus throttling-type parameters are the ones of interest with full forcing. In full throttling, we seek to minimize --across all starting sets-- the sum of the cardinality of that set and the propagation time that results. On trees, the full throttling number is equivalent to the throttling numbers of several other graph processes, such the game of cops and robbers, and the distance domination number (alternately, the $k$-radius) of a graph. For all of these, it is known that maximum possible throttling number for a tree on $n$ vertices is somewhere between $1.4502\\sqrt{n}$ and $\\frac{\\sqrt{14}}{2}\\sqrt{n}$, with the former exhibited by a family of spiders. After introducing some new ideas and methods for working with throttling on trees, this thesis determines the exact full throttling number of all balanced spiders (trees with equal-length paths extending from a center vertex), and proves that their full throttling numbers are bounded above by that of paths of the same order $n$, which are known to have full throttling number $\\lc\\sqrt{2n}-\\frac{1}{2}\\rc$.The variant called \\emph{Probabilistic zero forcing} takes a non-deterministic spin on the standard zero forcing color change rule. Here, the probability that a blue vertex forces one of its white neighbors is based on what proportion of the blue vertex's closed neighborhood is already blue. In the case where a vertex is the \\emph{only} white neighbor of a blue vertex, that probability is one; making that specific force identical to the standard zero forcing color change rule. This variant is well suited to modeling scenarios of virus or rumor spreading. As with full forcing, any single vertex in a connected graph constitutes a probabilistic zero forcing set. As such, the parameter to be studied is that of expected propagation time of a graph, $\\ept(G)$: where propagation time of a vertex is treated as a discrete random variable, and we examine the expected value of that random variable. In this thesis we explore the effects that certain graph operations may have on the expected propagation time of a given graph, use examples to illustrate that \\emph{all} of the operations can result in an increase or decrease from $\\ept(G)$, and discuss how large such changes can be relative to the order of the graph.

ISBN: 9798819384749Subjects--Topical Terms:

515831
Mathematics.
Subjects--Index Terms:

Full forcing

Propagation Processes: Full Throttling and Probabilistic Zero Forcing.
LDR:05172nmm a2200385 4500 001 2349722
005 20221003074939.5
008 241004s2022 eng d
020 $a 9798819384749
035 $a (MiAaPQ)AAI29068394
035 $a AAI29068394
040 $a MiAaPQ $c MiAaPQ
100 1 $a Ross, Michael Steven. $0 (orcid)0000-0003-3342-5577 $3 3689141
245 1 0 $a Propagation Processes: Full Throttling and Probabilistic Zero Forcing.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2022
300 $a 54 p.
500 $a Source: Dissertations Abstracts International, Volume: 83-12, Section: B.
500 $a Advisor: Hogben, Leslie.
502 $a Thesis (Ph.D.)--Iowa State University, 2022.
506 $a This item must not be sold to any third party vendors.
520 $a Zero forcing is a process that arose in many contexts, including mathematical physics under the name ``graph infection", in graph searching problems in computer science, and in linear algebra as an upper bound on the multiplicity of an eigenvalue of a matrix described by a graph. With standard zero forcing, one colors some initial vertices of a graph blue, and whenever a vertex is the only white neighbor of a blue vertex, it is also colored blue. The diverse origins of zero forcing have inspired many variants of this color change rule. From its linear algebra aspect comes positive semidefinite zero forcing, where in each time step one first splits the graph obtained by deleting the blue vertices across its connected components and then does the standard zero forcing rule on the induced subgraph on the vertices of each component together with the blue vertices of the graph. On the graph searching side, the game of cops and robbers and its variants have many similar properties, and standard zero forcing is equivalent to fast mixed graph searching. In each case there are a few core aspects that are studied for a given graph: the number of initial vertices required to complete the process, the amount of time required for the process to complete given a specific set of starting vertices, and ``throttling" parameters that seek to minimize some combination of the two (typically the sum).Building on the behavior that positive semidefinite zero forcing exhibits on trees, we introduce full forcing, where blue vertices will force every neighbor they have every round. Trivially, any single vertex in a connected graph is a full forcing set, and the minimum propagation time across singleton sets is just the radius of the graph; thus throttling-type parameters are the ones of interest with full forcing. In full throttling, we seek to minimize --across all starting sets-- the sum of the cardinality of that set and the propagation time that results. On trees, the full throttling number is equivalent to the throttling numbers of several other graph processes, such the game of cops and robbers, and the distance domination number (alternately, the $k$-radius) of a graph. For all of these, it is known that maximum possible throttling number for a tree on $n$ vertices is somewhere between $1.4502\\sqrt{n}$ and $\\frac{\\sqrt{14}}{2}\\sqrt{n}$, with the former exhibited by a family of spiders. After introducing some new ideas and methods for working with throttling on trees, this thesis determines the exact full throttling number of all balanced spiders (trees with equal-length paths extending from a center vertex), and proves that their full throttling numbers are bounded above by that of paths of the same order $n$, which are known to have full throttling number $\\lc\\sqrt{2n}-\\frac{1}{2}\\rc$.The variant called \\emph{Probabilistic zero forcing} takes a non-deterministic spin on the standard zero forcing color change rule. Here, the probability that a blue vertex forces one of its white neighbors is based on what proportion of the blue vertex's closed neighborhood is already blue. In the case where a vertex is the \\emph{only} white neighbor of a blue vertex, that probability is one; making that specific force identical to the standard zero forcing color change rule. This variant is well suited to modeling scenarios of virus or rumor spreading. As with full forcing, any single vertex in a connected graph constitutes a probabilistic zero forcing set. As such, the parameter to be studied is that of expected propagation time of a graph, $\\ept(G)$: where propagation time of a vertex is treated as a discrete random variable, and we examine the expected value of that random variable. In this thesis we explore the effects that certain graph operations may have on the expected propagation time of a given graph, use examples to illustrate that \\emph{all} of the operations can result in an increase or decrease from $\\ept(G)$, and discuss how large such changes can be relative to the order of the graph.
590 $a School code: 0097.
650 4 $a Mathematics. $3 515831
650 4 $a Statistics. $3 517247
650 4 $a Statistical physics. $3 536281
650 4 $a Applied mathematics. $3 2122814
653 $a Full forcing
653 $a Graph searching
653 $a Probabilistic zero forcing
653 $a Rumor spreading
653 $a Throttling
653 $a Zero forcing
690 $a 0405
690 $a 0217
690 $a 0463
690 $a 0364
710 2 0 $a Iowa State University. $b Mathematics. $3 1266625
773 0 $t Dissertations Abstracts International $g 83-12B.
790 $a 0097
791 $a Ph.D.
792 $a 2022
793 $a English