Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6872077 | Discrete Applied Mathematics | 2016 | 17 Pages |
Abstract
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âWi is the only white neighbor of some bâB in the graph G[BâªWi], then we change w to blue. A minimum positive semidefinite zero forcing set (PSDZFS) is a set of blue vertices that colors the entire graph blue and has minimum cardinality. 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. It is conjectured that every propagation time between the minimum and maximum propagation time is attainable by some minimum PSDZFS (this is not the case for the standard color-change rule). Tools are developed that aid in the computation of PSD propagation time. Several graph families and graphs with extreme PSD propagation times (|G|â2,|G|â1,1,0) are analyzed.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Nathan Warnberg,