#### Degree Type

Dissertation

#### Date of Award

2014

#### Degree Name

Doctor of Philosophy

#### Department

Mathematics

#### First Advisor

Leslie Hogben

#### Abstract

Let G be a simple, undirected graph. Positive semidefinite (PSD) zero forcing on G is based on the following color-change rule: Let W_{1},W_{2}, ..., W_{k} be the sets of vertices of the k connected components in G - B (where B is a set of blue vertices). If w is in W_{i} and is the only white neighbor of some blue vertex b in the graph G[B_{i}] (where B_{i} is the set of blue vertices of B and the white vertices of W_{i}), then we change w to blue. A positive semidefinite zero forcing set (PSDZFS) is a set of blue vertices that colors the entire graph blue. The positive semidefinite zero forcing number, denoted Z_{+}(G), is the minimum cardinality of a positive semidefinite zero forcing set. The PSD propagation time of a PSDZFS B of graph G is the minimum number of iterations that it takes to color the entire graph blue, starting with B blue, such that at each iteration as many vertices are colored blue as allowed by the color-change rule. The minimum and maximum PSD propagation times are taken over all minimum PSD zero forcing sets of the graph. The PSD propagation time interval of a graph G is the set of integers [pt_{+}(G),pt_{+}(G) +1,...,PT_{+}(G)]. It is believed that every integer in the interval is achievable by some minimum PSDZFS. This thesis develops tools to analyze the minimum and maximum PSD propagation time, tools for analyzing the PSD propagation time interval and applies these tools to study the PSD propagation time of many graph families.

#### DOI

https://doi.org/10.31274/etd-180810-2270

#### Copyright Owner

Nathan Warnberg

#### Copyright Date

2014

#### Language

en

#### File Format

application/pdf

#### File Size

89 pages

#### Recommended Citation

Warnberg, Nathan, "Positive semidefinite propagation time" (2014). *Graduate Theses and Dissertations*. 13706.

https://lib.dr.iastate.edu/etd/13706