Zero forcing parameters and minimum rank problems

DOI10.1016/J.LAA.2010.03.008MaRDI QIDQ975607zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1003.2028, https://lib.dr.iastate.edu/math_pubs/68

zbMATH Keywords

maximum nullityminimum rankzero forcing numberpositive semidefinite minimum rankpositive semidefinite zero forcing numberordered set numberpositive semidefinite maximum nullity

Mathematics Subject Classification ID

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)

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.

Recommendations

• Positive semidefinite maximum nullity and zero forcing number
• On minimum rank and zero forcing sets of a graph
• Zero forcing sets and the minimum rank of graphs
• Minimum rank, maximum nullity and zero forcing number for selected graph families
• Positive semidefinite zero forcing

Cites work

• Computation of minimal rank and path cover number for certain graphs
• Graphs whose positive semi-definite matrices have nullity at most two
• Linearly independent vertices and minimum semidefinite rank
• Lower bounds in minimum rank problems
• Maximum nullity of outerplanar graphs and the path cover number
• Multiplicities of eigenvalues and tree-width of graphs
• Olga, matrix theory and the Taussky unification problem
• On the Minimum Rank Among Positive Semidefinite Matrices with a Given Graph
• On the maximum positive semi-definite nullity and the cycle matroid of graphs
• On the minimum rank of not necessarily symmetric matrices: A preliminary study
• The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree
• The minimum rank of symmetric matrices described by a graph: a survey
• Zero forcing sets and the minimum rank of graphs

Cited in

(only showing first 100 items - show all)

• On the zero forcing number and spectral radius of graphs
• Throttling positive semidefinite zero forcing propagation time on graphs
• Note on positive semidefinite maximum nullity and positive semidefinite zero forcing number of partial 2-trees
• Bounds on the sum of minimum semidefinite rank of a graph and its complement
• Maximum nullity and zero forcing number of graphs with rank at most 4
• Odd cycle zero forcing parameters and the minimum rank of graph blowups
• Infection in hypergraphs
• Minimum rank with zero diagonal
• On the relationships between zero forcing numbers and certain graph coverings
• Lower bounds in minimum rank problems
• Finding low-rank solutions of sparse linear matrix inequalities using convex optimization
• Complexity and computation of connected zero forcing
• Maximum nullity and zero forcing of circulant graphs
• Strong structural controllability and leader selection for multi-agent systems with unidirectional topology
• On the graph complement conjecture for minimum semidefinite rank
• On the relationship between the zero forcing number and path cover number for some graphs
• Computational approaches for zero forcing and related problems
• A new lower bound for the positive semidefinite minimum rank of a graph
• Zero forcing number, Grundy domination number, and their variants
• On the complexity of the positive semidefinite zero forcing number
• Positive zero forcing and edge clique coverings
• Positive semidefinite maximum nullity and zero forcing number
• On minimum rank and zero forcing sets of a graph
• Induced trees, minimum semidefinite rank, and zero forcing
• Leader selection for strong structural controllability of single-integrator multi-agent systems
• Zero forcing number, path cover number, and maximum nullity of cacti
• On the singularity of graphs: zero forcing parameters
• Zero forcing sets and the minimum rank of graphs
• A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs
• Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph
• A technique for computing the zero forcing number of a graph with a cut-vertex
• Constructing a controllable graph under edge constraints
• On zero forcing number of graphs and their complements
• The inverse eigenvalue problem of a graph: multiplicities and minors
• Bounds for minimum semidefinite rank from superpositions and cutsets
• Grundy dominating sequences and zero forcing sets
• Effects of vertex degrees on the zero-forcing number and propagation time of a graph
• Using a new zero forcing process to guarantee the strong Arnold property
• The minimum semidefinite rank of a triangle-free graph
• Throttling for the game of cops and robbers on graphs
• Propagation time for zero forcing on a graph
• Parameters related to tree-width, zero forcing, and maximum nullity of a graph
• 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
• Using variants of zero forcing to bound the inertia set of a graph
• Minimum rank, maximum nullity and zero forcing number for selected graph families
• Positive semidefinite zero forcing
• Bounds on minimum semidefinite rank of graphs
• Critical ideals, minimum rank and zero forcing number
• The minimum rank problem for circulants
• Maximum nullity and zero forcing number on graphs with maximum degree at most three
• Lower bounds for minimum semidefinite rank from orthogonal removal and chordal supergraphs
• Positive semidefinite propagation time
• Lower bounds for positive semidefinite zero forcing and their applications
• On the complexity of failed zero forcing
• The complexity of the positive semidefinite zero forcing
• Families of graphs with maximum nullity equal to zero forcing number
• Path cover number, maximum nullity, and zero forcing number of oriented graphs and other simple digraphs
• Upper bounds for positive semidefinite propagation time
• Tree cover number and maximum semidefinite nullity of some graph classes
• Positive semidefinite zero forcing: complexity and lower bounds
• Zero forcing sets and bipartite circulants
• Tight frame graphs arising as line graphs
• Positive semidefinite zero forcing numbers of two classes of graphs
• The sieving process and lower bounds for the minimum rank problem
• Minimum rank and zero forcing number for butterfly networks
• Isomorphisms and properties of TAR graphs for zero forcing and other \(X\)-set parameters
• Note on forcing problem of trees
• The zero forcing polynomial of a graph
• The zero forcing number of graphs with the matching number and the cyclomatic number
• Improved Computational Approaches and Heuristics for Zero Forcing
• Cup stacking in graphs
• Proper colorings from positive semidefinite zero forcing sets
• Grundy domination and zero forcing in Kneser graphs
• A computational comparison of compact MILP formulations for the zero forcing number
• A New Lower Bound for Positive Zero Forcing
• Throttling processes equivalent to full throttling on trees
• Failed power domination on graphs
• Zero forcing number, maximum nullity, and path cover number of subdivided graphs
• Vector representations of graphs and distinguishing quantum product states with one-way LOCC
• Fuzzification of Zero Forcing Process
• The \((d-2)\)-leaky forcing number of \(Q_d\) and \(\ell\)-leaky forcing number of \(GP(n,1)\)
• Orthogonal representations of Steiner triple system incidence graphs
• Brushing number and zero-forcing number of graphs and their line graphs
• Ordered multiplicity inverse eigenvalue problem for graphs on six vertices
• Propagation time for probabilistic zero forcing
• Sparks of symmetric matrices and their graphs
• Failed zero forcing numbers of Kneser graphs, Johnson graphs, and hypercubes
• Well-forced graphs
• Zero forcing with random sets
• Properties of a \(q\)-analogue of zero forcing
• Connected zero forcing sets and connected propagation time of graphs
• Spectral arbitrariness for trees fails spectacularly
• On the zero forcing number of a graph involving some classical parameters
• \(k\)-forcing number for Cartesian product of some graphs
• A zero forcing technique for bounding sums of eigenvalue multiplicities
• Bounds on expected propagation time of probabilistic zero forcing
• Zero forcing number of a graph in terms of the number of pendant vertices
• Identifying combinatorially symmetric hidden Markov models

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)