2012/11/19 by Steve Butler, Butler, Steve, Jason Grout +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Combinatorics (math.CO) #Discrete mathematics #Eigenvalues and eigenvectors #FOS: Mathematics #Forcing (mathematics) #Graph #Graph Labeling and Dimension Problems #Graph theory and applications #Inertia #Integral graph #Line graph #Mathematical analysis #Mathematics #Physics #Upper and lower bounds #Voltage graph #Zero (linguistics) #math.CO
paper · pdf · doi:10.48550/arxiv.1211.4618
16 pages, lots of figures
arxiv created 2012/11/19 · openalex publication_date 2012/11/19 · arxiv updated 2012/11/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Zero forcing is a combinatorial game played on a graph with a goal of turning all of the vertices of the graph black while having to use as few "unforced" moves as possible. This leads to a parameter known as the zero forcing number which can be used to give an upper bound for the maximum nullity of a matrix associated with the graph. We introduce a new variation on the zero forcing game which can be used to give an upper bound for the maximum nullity of a matrix associated with a graph that has q negative eigenvalues. This gives some limits to the number of positive eigenvalues that such a graph can have and so can be used to form lower bounds for the inertia set of a graph.