The minimum rank of symmetric matrices described by a graph: A survey☆

By Shaun M. Fallat, Leslie Hogben. 2007

267 citations recorded by the source corpus.

Abstract The minimum rank of a simple graph G is defined to be the smallest possible rank over all symmetric real matrices whose ijth entry (for i ≠ j ) is nonzero whenever { i , j } is an edge in G and is zero otherwise. This paper surveys the current state of knowledge on the problem of determining the minimum rank of a graph and related issues.

Subfields: Computational Theory and Mathematics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/18ea2d48ec58223f69c980a25b622b686199a72f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Geometry and Topology

Citations in the corpus

Spectra of Graphs (2011, background): “[2, 164]) Let KΓ denote the class of real symmetric matrices M indexed by V Γ such that Muv = 0 if u 6∼ v, and Muv 6= 0 if u ∼ v (nothing is required for the diagonal of M).”
Zero forcing parameters and minimum rank problems (2010, background): “shed by induction on |T|: If v is a leaf, it forces its neighbor; if not a decomposition takes place. In either case smaller tree(s) are obtained. It has been known for a long time (see, for example, [7]) that MC +(T) = 1, but the use of Z+ provides an easy proof of this result, because MC +(T) = 1 ”
Minimum rank of skew-symmetric matrices described by a graph (2010, background): “This problem has been studied extensively and generalized to symmetric matrices over other fields; see [9] for a survey of known results and a discussion of the motivation for the minimum rank problem.”
SPECTRAL GRAPH THEORY AND THE INVERSE EIGENVALUE PROBLEM OF A GRAPH (2005, background): “See [15] for a more extensive survey of known results and discussion of the motivation for the minimum rank problem; an extensive bibliography is also provided there.”
On the minimum rank of not necessarily symmetric matrices : a preliminary study (2009, background): “This problem arose from the study of possible eigenvalues of real symmetric matrices described by a graph and has received considerable attention over the last ten years (see [7] for a survey with an extensive bibliography).”
Minimum number of distinct eigenvalues of graphs (2013, background): “It is well known that for all graphs G, mr(G) ≤ cc(G); see [7], and thus, we have the following corollary.”
An upper bound for the minimum rank of a graph (2008, background): “See [7] for a survey of known results and discussion of the motivation for the minimum rank problem; an extensive bibliography is also provided there.”
Zero forcing and power domination for graph products (2018, background): “The study of maximum nullity, or equivalently, maximum multiplicity of an eigenvalue, was motivated by the inverse eigenvalue problem of a graph (see [13] and [12] for surveys of results on maximum nullity and zero forcing containing more than a hundred references).”