USING VARIANTS OF ZERO FORCING TO BOUND THE INERTIA SET OF A GRAPH

作者：Butler Steve^*; Grout Jason; Hall H Tracy

来源：Electronic Journal of Linear Algebra, 2015, 30(1): 1-18.

DOI：10.13001/1081-3810.2900

• Zero forcing
• Inertia sets
• Isotropic subspaces

Zero forcing is a combinatorial game played on a graph with a goal of changing the color of every vertex at minimal cost. This leads to a parameter known as the zero forcing number that can be used to give an upper bound for the maximum nullity of a matrix associated with the graph. A variation on the zero forcing game is introduced that can be used to give an upper bound for the maximum nullity of such a matrix when it is constrained to have exactly q negative eigenvalues.
This constrains the possible inertias that a matrix associated with a graph can achieve and gives a method to construct lower bounds on the inertia set of a graph (which is the set of all possible pairs (p, q) where p is the number of positive eigenvalues and q is the number of negative eigenvalues).

• 出版日期2015-1