Positive semidefinite propagation time
Is Version Of
Let G be a simple, undirected graph. Positive semidefinite (PSD) zero forcing on G is based on the following color-change rule: Let W1,W2, ..., Wk 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 Wi and is the only white neighbor of some blue vertex b in the graph G[Bi] (where Bi is the set of blue vertices of B and the white vertices of Wi), 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.