Variants on the minimum rank problem: A survey II

Abstract

The minimum rank problem for a (simple) graph $G$ is to determine the smallest possible rank over all real symmetric matrices whose $ij$th entry (for $i\ne j$) is nonzero whenever $\{i,j\}$ is an edge in $G$ 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.

3 figures This survey was originally posted in Feb. 2011. However, this paper is now outdated and interested readers should consult Chapter 46 of the Handbook of Linear Algebra, 2nd Edition for a more recent and comprehensive survey

References in corpus (3)

• Full control by locally induced relaxation
• Expected values of parameters associated with the minimum rank of a graph
• The inverse inertia problem for graphs

Cited by in corpus (10)

• Probabilistic Zero Forcing in Graphs
• Metric Dimension and Zero Forcing Number of Two Families of Line Graphs
• Vector Representations of Graphs and Distinguishing Quantum Product States with One-way LOCC
• A new graph parameter related to bounded rank positive semidefinite matrix completions
• Complexity of the positive semidefinite matrix completion problem with a rank constraint
• On Zero Forcing Number of Functigraphs
• On the zero forcing number of corona and lexicographic product of graphs
• Minimum Vector Rank and Complement Critical Graphs
• Zero forcing for sign patterns
• Minimum number of distinct eigenvalues of graphs