Zero forcing parameters and minimum rank problems
From MaRDI portal
Publication:975607
DOI10.1016/J.LAA.2010.03.008zbMATH Open1209.05139arXiv1003.2028OpenAlexW2099618798MaRDI QIDQ975607FDOQ975607
P. van den Driessche, Francesco Barioli, Wayne Barrett, Bryan L. Shader, Hein van der Holst, Shaun M. Fallat, Leslie Hogben, H. Tracy Hall
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)
- Vector representations of graphs and distinguishing quantum product states with one-way LOCC
- Probabilistic zero forcing on random graphs
- The inverse eigenvalue problem of a graph: multiplicities and minors
- Title not available (Why is that?)
- Grundy domination and zero forcing in Kneser graphs
- Upper bounds for positive semidefinite propagation time
- The zero forcing polynomial of a graph
- Brushing number and zero-forcing number of graphs and their line graphs
- Title not available (Why is that?)
- A lower bound on the zero forcing number
- Positive Semidefinite Zero Forcing: Complexity and Lower Bounds
- Bounds on minimum semidefinite rank of graphs
- 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
- Maximum nullity and zero forcing number on graphs with maximum degree at most three
- Strong Structural Controllability and Leader Selection for Multi-agent Systems with Unidirectional Topology
- The minimum rank problem for circulants
- Parameters Related to Tree‐Width, Zero Forcing, and Maximum Nullity of a Graph
- 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
- 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
- A technique for computing the zero forcing number of a graph with a cut-vertex
- Propagation time for zero forcing on a graph
- Minimum rank with zero diagonal
- A new lower bound for the positive semidefinite minimum rank of a graph
- Compressed cliques graphs, clique coverings and positive zero forcing
- Positive Zero Forcing and Edge Clique Coverings
- Throttling positive semidefinite zero forcing propagation time on graphs
- On the complexity of failed zero forcing
- Zero forcing sets and bipartite circulants
- Line graphs: Their maximum nullities and zero forcing numbers
- Computational approaches for zero forcing and related problems
- On the complexity of the positive semidefinite zero forcing number
- Positive semidefinite propagation time
- Ordered multiplicity inverse eigenvalue problem for graphs on six vertices
- Complexity and computation of connected zero forcing
- Connected zero forcing sets and connected propagation time of graphs
- Note on forcing problem of trees
- On the relationship between the zero forcing number and path cover number for some graphs
- Constructing a controllable graph under edge constraints
- Critical ideals, minimum rank and zero forcing number
- Finding Low-rank Solutions of Sparse Linear Matrix Inequalities using Convex Optimization
- 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
- 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
- The Complexity of the Positive Semidefinite Zero Forcing
- 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
- A zero forcing technique for bounding sums of eigenvalue multiplicities
- Bounds on expected propagation time of probabilistic zero forcing
- Bounds for minimum semidefinite rank from superpositions and cutsets
- Cup stacking in graphs
- Propagation time for probabilistic zero forcing
- Positive semidefinite zero forcing numbers of two classes of graphs
- Propagation tree decompositions and linearly independent vertices
- A computational comparison of compact MILP formulations for the zero forcing number
- On the zero forcing number of a graph involving some classical parameters
- 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
- Tight Frame Graphs Arising as Line Graphs
- On leaky forcing and resilience
- Strong structural controllability of colored structured systems
- Isomorphisms and properties of TAR graphs for zero forcing and other \(X\)-set parameters
- Fuzzification of Zero Forcing Process
- 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
- Multi-color forcing in graphs
- On the zero forcing number of the complement of graphs with forbidden subgraphs
- Failed zero forcing and critical sets on directed graphs
- Throttling processes equivalent to full throttling on trees
- The zero forcing number of claw-free cubic graphs
- Sparks of symmetric matrices and their graphs
- Zero forcing with random sets
- k-Forcing number for Cartesian product of some graphs
- Well-forced graphs
- On the length of L-Grundy sequences
- A New Lower Bound for Positive Zero Forcing
- On the zero forcing number of generalized Sierpinski graphs
- Orthogonal representations of Steiner triple system incidence graphs
- Zero forcing number of a graph in terms of the number of pendant vertices
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)
