Using variants of zero forcing to bound the inertia set of a graph

DOI10.13001/1081-3810.2900MaRDI QIDQ3448171zbMATH OpenOpenAlexFDO

Authors Steve Butler, Jason Grout, H. Tracy Hall

Publication date 23 October 2015

Published in The Electronic Journal of Linear Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1211.4618, https://semanticscholar.org/paper/db56724bb16334bcc02a22b63762b8677591cf86

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

inertia setsisotropic subspaceszero forcing

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Games on graphs (graph-theoretic aspects) (05C57) Vector spaces, linear dependence, rank, lineability (15A03) Games involving graphs (91A43)

Abstract: 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.

Recommendations

• Positive semidefinite maximum nullity and zero forcing number
• Zero forcing parameters and minimum rank problems
• Zero forcing for sign patterns
• On the singularity of graphs: zero forcing parameters
• The inverse eigenvalue problem of a graph

Cited in

(15)

• Computational approaches for zero forcing and related problems
• The zero forcing polynomial of a graph
• A zero forcing technique for bounding sums of eigenvalue multiplicities
• Complexity and computation of connected zero forcing
• Properties of a \(q\)-analogue of zero forcing
• A reduction procedure for the Colin de Verdière number of a graph
• The maximum multiplicity of the largest \(k\)-th eigenvalue in a matrix whose graph is acyclic or unicyclic
• Reconfiguration graphs of zero forcing sets
• Constructions of cospectral graphs with different zero forcing numbers
• A note on variants of zero forcing
• An integer program for positive semidefinite zero forcing in graphs
• The \(q\)-analogue of zero forcing for certain families of graphs
• The classification of graphs on eight vertices with coinciding zero forcing number and maximum nullity
• Exploring the influence of graph operations on zero forcing sets
• Zero forcing irredundant sets

Describes a project that uses

Uses Software

• Minimum Rank
• SageMath
• GitHub

This page was built for publication: Using variants of zero forcing to bound the inertia set of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3448171)