The minimum rank of symmetric matrices described by a graph: a survey
From MaRDI portal
Publication:996311
Abstract: The minimum rank problem for a (simple) graph is to determine the smallest possible rank over all real symmetric matrices whose th entry (for ) is nonzero whenever is an edge in and is zero otherwise. This paper surveys the many developments on the (standard) minimum rank problem and its variants since the survey paper cite{FH}. In particular, positive semidefinite minimum rank, zero forcing parameters, and minimum rank problems for patterns are discussed.
Recommendations
Cites work
- scientific article; zbMATH DE number 1303522 (Why is no real title available?)
- scientific article; zbMATH DE number 475583 (Why is no real title available?)
- scientific article; zbMATH DE number 790476 (Why is no real title available?)
- scientific article; zbMATH DE number 5065241 (Why is no real title available?)
- scientific article; zbMATH DE number 3414355 (Why is no real title available?)
- A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs
- A characterization of tridiagonal matrices
- A typical vertex of a tree
- A variant on the graph parameters of Colin de Verdiere: Implications to the minimum rank of graphs
- Biclique decompositions and Hermitian rank
- Computation of minimal rank and path cover number for certain graphs
- Eigensharp Graphs: Decomposition into Complete Bipartite Subgraphs
- Eigenvalues and partitionings of the edges of a graph
- Estimation of the maximum multiplicity of an eigenvalue in terms of the vertex degrees of the graph of a matrix
- Forbidden minors for the class of graphs \(G\) with \(\xi (G) \leqslant 2\)
- Graphs whose minimal rank is two
- Graphs whose minimal rank is two: The finite fields case
- Graphs whose positive semi-definite matrices have nullity at most two
- Hermitian Matrices, Eigenvalue Multiplicities, and Eigenvector Components
- Inverse eigenvalue problems and lists of multiplicities of eigenvalues for matrices whose graph is a tree: The case of generalized stars and double generalized stars.
- Linearly independent vertices and minimum semidefinite rank
- Minimum rank and maximum eigenvalue multiplicity of symmetric tree sign patterns
- Minimum rank of a graph over an arbitrary field
- Minimum-rank matrices with prescribed graph
- Multiplicities of eigenvalues and tree-width of graphs
- On Fiedler's characterization of tridiagonal matrices over arbitrary fields
- On a characterization of tridiagonal matrices by M. Fiedler
- On minimal rank over finite fields
- On the Addressing Problem for Loop Switching
- On the Eigenvalues and Eigenvectors of a Class of Matrices
- On the Minimum Rank Among Positive Semidefinite Matrices with a Given Graph
- On the Shannon capacity of a graph
- On the difference between the maximum multiplicity and path cover number for tree-like graphs
- On the eigenvalues of generalized and double generalized stars
- On the minimum number of distinct eigenvalues for a symmetric matrix whose graph is a given tree
- On the minimum rank of the join of graphs and decomposable graphs
- On the minimum semidefinite rank of a simple graph
- On the possible multiplicities of the eigenvalues of a Hermitian matrix whose graph is a tree
- On the rank of a matrix associated with a graph.
- On two conjectures regarding an inverse eigenvalue problem for acyclic symmetric matrices
- Smith normal form and acyclic matrices
- Spectral graph theory and the inverse eigenvalue problem of a graph
- Spectral multiplicity and splitting results for a class of qualitative matrices
- Spektren endlicher Grafen
- The Parter--Wiener Theorem: Refinement and Generalization
- The graphs for which the maximum multiplicity of an eigenvalue is two
- The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree
- Unitary matrix digraphs and minimum semidefinite rank
Cited in
(only showing first 100 items - show all)- Zero forcing for sign patterns
- Minimum rank and zero forcing number for butterfly networks
- Uniform forcing and immune sets in graphs and hypergraphs
- Tree covers of graphs and their linear preservers
- Improved Computational Approaches and Heuristics for Zero Forcing
- Finding low-rank solutions of sparse linear matrix inequalities using convex optimization
- Achievable multiplicity partitions in the inverse eigenvalue problem of a graph
- Grundy domination and zero forcing in Kneser graphs
- Minimum rank of powers of trees
- Vector representations of graphs and distinguishing quantum product states with one-way LOCC
- Zero forcing and maximum nullity for hypergraphs
- On orthogonal matrices with zero diagonal
- Sparks of symmetric matrices and their graphs
- Failed zero forcing numbers of Kneser graphs, Johnson graphs, and hypercubes
- Well-forced graphs
- The nullity of bicyclic signed graphs
- The strong spectral property for graphs
- Connected zero forcing sets and connected propagation time of graphs
- On the minimum number of distinct eigenvalues of a threshold graph
- Corrigendum to: ``Achievable multiplicity partitions in the inverse eigenvalue problem of a graph
- Minimum-rank and maximum-nullity of graphs and their linear preservers
- A note on the nullity of unicyclic signed graphs
- Conformally covariant operators and conformal invariants on weighted graphs
- On the rank of a matrix associated with a graph.
- A note on universally optimal matrices and field independence of the minimum rank of a graph
- A zero forcing technique for bounding sums of eigenvalue multiplicities
- Zero forcing number of a graph in terms of the number of pendant vertices
- Using Markov chains to determine expected propagation time for probabilistic zero forcing
- Spectral aspects of symmetric matrix signings
- Relation between the rank of a signed graph and the rank of its underlying graph
- Reconfiguration graphs of zero forcing sets
- On the rank spread of graphs
- Critical exponents of graphs
- The minimum rank of a sign pattern matrix with a 1-separation
- Maximum nullity, zero forcing number and propagation time of \(\ell\)-path graphs
- A Nordhaus-Gaddum conjecture for the minimum number of distinct eigenvalues of a graph
- The average cut-rank of graphs
- The inverse eigenvalue problem of a graph: multiplicities and minors
- Chordal graphs and distinguishability of quantum product states
- Uniformly sparse graphs and matrices
- An integer program for positive semidefinite zero forcing in graphs
- The maximum multiplicity of the largest \(k\)-th eigenvalue in a matrix whose graph is acyclic or unicyclic
- Immune sets in monotone infection rules. Characterization and complexity
- Line graphs: their maximum nullities and zero forcing numbers.
- Maximum generic nullity of a graph
- Speeding up finite-time consensus via minimal polynomial of a weighted graph -- a numerical approach
- On leaky forcing and resilience
- The critical exponent: a novel graph invariant
- An ensemble of high rank matrices arising from tournaments
- The minimum rank problem for circulants
- The strong spectral property of graphs: graph operations and barbell partitions
- Generalizations of the strong Arnold property and the minimum number of distinct eigenvalues of a graph
- Techniques for determining equality of the maximum nullity and the zero forcing number of a graph
- Approximating the minimum rank of a graph via alternating projection
- Frame graph
- Almost full rank matrices arising from transitive tournaments
- Minimum rank of graphs with loops
- On symmetric matrices with indeterminate leading diagonals
- The inertia set of a signed graph
- Maximum nullity and zero forcing number of graphs with rank at most 4
- Infection in hypergraphs
- Expected values of parameters associated with the minimum rank of a graph
- Zero forcing number, constrained matchings and strong structural controllability
- A new graph parameter related to bounded rank positive semidefinite matrix completions
- Minimum-rank matrices with prescribed graph
- Lower bounds in minimum rank problems
- Complexity and computation of connected zero forcing
- Minimum rank of edge subdivisions of graphs
- On the graph complement conjecture for minimum semidefinite rank
- An upper bound for the minimum rank of a graph
- On the nullity of graphs with pendant trees
- The inverse eigenvalue and inertia problems for minimum rank two graphs
- A new lower bound for the positive semidefinite minimum rank of a graph
- Spectral aspects of symmetric matrix signings
- Computing inertia sets using atoms
- Minimum rank of outerplanar graphs
- Linear algebraic methods in communication complexity
- On the graph complement conjecture for minimum rank
- On the minimum rank of the third power of a starlike tree
- On the tree cover number of a graph
- Minimum rank of skew-symmetric matrices described by a graph
- On minimum rank and zero forcing sets of a graph
- Techniques for determining the minimum rank of a small graph
- Minimum rank of matrices described by a graph or pattern over the rational, real and complex numbers
- A characterization of signed planar graphs with rank at most 4
- Zero forcing parameters and minimum rank problems
- 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
- Determinants of grids, tori, cylinders and Möbius ladders
- Minimum rank problems
- On the minimum rank of the join of graphs and decomposable graphs
- The inverse inertia problem for the complements of partial \(k\)-trees
- Minimum rank of graphs powers family
- On acyclic and unicyclic graphs whose minimum rank equals the diameter
- Zero forcing and power domination for graph products
- On zero forcing number of graphs and their complements
- On the determinant of bipartite graphs
- Bounds for minimum semidefinite rank from superpositions and cutsets
This page was built for publication: The minimum rank of symmetric matrices described by a graph: a survey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q996311)