Zero forcing parameters and minimum rank problems
From MaRDI portal
Publication:975607
DOI10.1016/J.LAA.2010.03.008zbMATH Open1209.05139arXiv1003.2028OpenAlexW2099618798MaRDI QIDQ975607FDOQ975607
Authors: Francesco Barioli, Shaun M. Fallat, H. Tracy Hall, Leslie Hogben, Hein van der Holst, Wayne Barrett, Bryan L. Shader, P. van den Driessche 
Publication date: 10 June 2010
Published in: Linear Algebra and its Applications (Search for Journal in Brave)
Abstract: The zero forcing number Z(G), which is the minimum number of vertices in a zero forcing set of a graph G, is used to study the maximum nullity / minimum rank of the family of symmetric matrices described by G. It is shown that for a connected graph of order at least two, no vertex is in every zero forcing set. The positive semidefinite zero forcing number Z_+(G) is introduced, and shown to be equal to |G|-OS(G), where OS(G) is the recently defined ordered set number that is a lower bound for minimum positive semidefinite rank. The positive semidefinite zero forcing number is applied to the computation of positive semidefinite minimum rank of certain graphs. An example of a graph for which the real positive symmetric semidefinite minimum rank is greater than the complex Hermitian positive semidefinite minimum rank is presented.
Full work available at URL: https://arxiv.org/abs/1003.2028
Recommendations
maximum nullityminimum rankzero forcing numberpositive semidefinite minimum rankpositive semidefinite zero forcing numberordered set numberpositive semidefinite maximum nullity
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Hermitian, skew-Hermitian, and related matrices (15B57) Vector spaces, linear dependence, rank, lineability (15A03)
Cites Work
- Zero forcing sets and the minimum rank of graphs
- Olga, matrix theory and the Taussky unification problem
- Computation of minimal rank and path cover number for certain graphs
- Multiplicities of eigenvalues and tree-width of graphs
- Graphs whose positive semi-definite matrices have nullity at most two
- On the maximum positive semi-definite nullity and the cycle matroid of graphs
- On the Minimum Rank Among Positive Semidefinite Matrices with a Given Graph
- The minimum rank of symmetric matrices described by a graph: a survey
- The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree
- Lower bounds in minimum rank problems
- Linearly independent vertices and minimum semidefinite rank
- On the minimum rank of not necessarily symmetric matrices: A preliminary study
- Maximum nullity of outerplanar graphs and the path cover number
Cited In (only showing first 100 items - show all)
- Finding low-rank solutions of sparse linear matrix inequalities using convex optimization
- Positive zero forcing and edge clique coverings
- The inverse eigenvalue problem of a graph: multiplicities and minors
- Positive semidefinite maximum nullity and zero forcing number
- Upper bounds for positive semidefinite propagation time
- Lower bounds in minimum rank problems
- Bounds on minimum semidefinite rank of graphs
- Maximum nullity and zero forcing number of graphs with rank at most 4
- On the graph complement conjecture for minimum semidefinite rank
- Leader selection for strong structural controllability of single-integrator multi-agent systems
- The minimum semidefinite rank of a triangle-free graph
- Minimum rank, maximum nullity and zero forcing number for selected graph families
- Maximum nullity and zero forcing number on graphs with maximum degree at most three
- On the singularity of graphs: zero forcing parameters
- The minimum rank problem for circulants
- Effects of vertex degrees on the zero-forcing number and propagation time of a graph
- Throttling for the game of cops and robbers on graphs
- Zero forcing number, path cover number, and maximum nullity of cacti
- Using a new zero forcing process to guarantee the strong Arnold property
- Families of graphs with maximum nullity equal to zero forcing number
- Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph
- On zero forcing number of graphs and their complements
- Fractional zero forcing via three-color forcing games
- Proof of a conjecture on the zero forcing number of a graph
- Failed skew zero forcing on a graph
- Tree cover number and maximum semidefinite nullity of some graph classes
- Note on positive semidefinite maximum nullity and positive semidefinite zero forcing number of partial 2-trees
- A technique for computing the zero forcing number of a graph with a cut-vertex
- Propagation time for zero forcing on a graph
- Bounds on the sum of minimum semidefinite rank of a graph and its complement
- Minimum rank with zero diagonal
- A new lower bound for the positive semidefinite minimum rank of a graph
- Throttling positive semidefinite zero forcing propagation time on graphs
- On minimum rank and zero forcing sets of a graph
- Zero forcing sets and the minimum rank of graphs
- On the complexity of failed zero forcing
- Zero forcing sets and bipartite circulants
- Computational approaches for zero forcing and related problems
- On the complexity of the positive semidefinite zero forcing number
- Positive semidefinite propagation time
- The complexity of the positive semidefinite zero forcing
- Strong structural controllability and leader selection for multi-agent systems with unidirectional topology
- Complexity and computation of connected zero forcing
- Using variants of zero forcing to bound the inertia set of a graph
- Maximum nullity and zero forcing of circulant graphs
- On the relationship between the zero forcing number and path cover number for some graphs
- Constructing a controllable graph under edge constraints
- Parameters related to tree-width, zero forcing, and maximum nullity of a graph
- Critical ideals, minimum rank and zero forcing number
- Positive semidefinite zero forcing: complexity and lower bounds
- Lower bounds for minimum semidefinite rank from orthogonal removal and chordal supergraphs
- On the relationships between zero forcing numbers and certain graph coverings
- Zero forcing number, Grundy domination number, and their variants
- Induced trees, minimum semidefinite rank, and zero forcing
- Grundy dominating sequences and zero forcing sets
- On the zero forcing number and spectral radius of graphs
- Lower bounds for positive semidefinite zero forcing and their applications
- Infection in hypergraphs
- Path cover number, maximum nullity, and zero forcing number of oriented graphs and other simple digraphs
- A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs
- Positive semidefinite zero forcing
- Odd cycle zero forcing parameters and the minimum rank of graph blowups
- Bounds for minimum semidefinite rank from superpositions and cutsets
- Cup stacking in graphs
- Vector representations of graphs and distinguishing quantum product states with one-way LOCC
- Propagation time for probabilistic zero forcing
- Probabilistic zero forcing on random graphs
- Positive semidefinite zero forcing numbers of two classes of graphs
- \(k\)-forcing number for Cartesian product of some graphs
- Propagation tree decompositions and linearly independent vertices
- Grundy domination and zero forcing in Kneser graphs
- A computational comparison of compact MILP formulations for the zero forcing number
- Zero forcing number of some families of graphs
- On the zero forcing number of generalized Sierpiński graphs
- The zero forcing polynomial of a graph
- Brushing number and zero-forcing number of graphs and their line graphs
- On the zero forcing number of a graph involving some classical parameters
- A lower bound on the zero forcing number
- Leaky forcing: a new variation of zero forcing
- Failed power domination on graphs
- Properties of a \(q\)-analogue of zero forcing
- Grundy domination and zero forcing in regular graphs
- Graph complement conjecture for classes of shadow graphs
- The zero forcing number of graphs with the matching number and the cyclomatic number
- Improved Computational Approaches and Heuristics for Zero Forcing
- Failed zero forcing numbers of Kneser graphs, Johnson graphs, and hypercubes
- Identifying combinatorially symmetric hidden Markov models
- On leaky forcing and resilience
- Strong structural controllability of colored structured systems
- Computing the zero forcing number for generalized Petersen graphs
- Techniques for determining equality of the maximum nullity and the zero forcing number of a graph
- Isomorphisms and properties of TAR graphs for zero forcing and other \(X\)-set parameters
- Fuzzification of Zero Forcing Process
- Line graphs: their maximum nullities and zero forcing numbers.
- Bounds on zero forcing using (upper) total domination and minimum degree
- Open global shadow graph and it’s zero forcing number
- Skew throttling
- Constructions of cospectral graphs with different zero forcing numbers
- Spectral arbitrariness for trees fails spectacularly
- The zero forcing span of a graph
This page was built for publication: Zero forcing parameters and minimum rank problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q975607)
