Upper bounds for PSD propagation time and zero forcing in shadow graphs

Yaqi Zhang

doi:10.17918/00001629

Zero forcing is a color changing process on the vertices of a graph. The zero forcing number of a graph is the minimum cardinality among the zero forcing sets, which are subsets of the vertices which have the property that as a starting set it will color the whole graph. A motivation for studying zero forcing is the study of minimum rank and maximum nullity of matrices with a given sparsity pattern. The zero forcing number provides an upper bound for the maximum nullity of a matrix whose off-diagonal non-zero entries are described by the graph. The study of zero forcing includes several questions regarding, for instance, the propagation time (pt₊(G)) of a graph G and a maximum failed zero forcing set. In this thesis, the tight upper bound pt₊(G) [less than or equal to] [rounded up][[[absolute value][V(G)] - Z₊(G)]/2] is established for the positive semidefinite propagation time of a graph G in terms of its positive semidefinite zero forcing number Z₊(G). To prove this bound, two methods of transforming one positive semidefinite zero forcing set into another and algorithms implementing these methods are presented. Consequences of the bound, including a tight Nordhaus-Gaddum sum upper bound on the positive semidefinite propagation time, are established. In order to study the maximum failed zero forcing set, we introduce a definition for the spark of a graph which is closely related to the notion of a fort, and we build a connection from the spark of the graph to the maximum failed zero forcing set size. In addition, we consider the full spark scenario for graphs. We also study how these quantities change when we replace a graph by its shadow graph, which is obtained from a graph G by adding for each vertex v of G a new vertex u, called the shadow vertex of v, and joining u to the neighbors of v in G. As the maximum nullity of a matrix is the maximum geometric multiplicity of zero as an eigenvalue, it is also natural to study the appearing multiplicities among the eigenvalues of the matrices. In the final chapter, we establish a connection between the number of distinct eigenvalues from level symmetric trees to that of a path, and present a conjecture for the minimal total eigenvalue multiplicities for a path along with some evidence in support of this conjecture.

Upper bounds for PSD propagation time and zero forcing in shadow graphs

Files and links (1)

Abstract

Metrics

Details

Upper bounds for PSD propagation time and zero forcing in shadow graphs

Files and links (1)

Abstract

Metrics

Details

Drexel University Social media