Computational and Theoretical Challenges for Computing the Minimum Rank of a Graph
- 1 November 2022
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 34 (6) , 2868-2872
Abstract
The minimum rank of a graph G is the minimum of the ranks of all symmetric adjacency matrices of G. We present a new combinatorial bound for the minimum rank of an arbitrary graph G based on enumerating certain subsets of vertices of G satisfying matroid theoretic properties. We also present some computational and theoretical challenges associated with computing the minimum rank. This includes a conjecture that this bound on the minimum rank actually holds with equality for all graphs.Keywords
This publication has 23 references indexed in Scilit:
- On the graph complement conjecture for minimum rankLinear Algebra and its Applications, 2012
- Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graphLinear Algebra and its Applications, 2012
- On minimum rank and zero forcing sets of a graphLinear Algebra and its Applications, 2010
- Lower Bounds in Minimum Rank ProblemsLinear Algebra and its Applications, 2010
- The graphs for which the maximum multiplicity of an eigenvalue is twoLinear and Multilinear Algebra, 2009
- Zero forcing sets and the minimum rank of graphsLinear Algebra and its Applications, 2008
- Forbidden minors for the class of graphs G withLinear Algebra and its Applications, 2007
- Computation of minimal rank and path cover number for certain graphsLinear Algebra and its Applications, 2004
- A typical vertex of a treeDiscrete Mathematics, 2001
- The maximum multiplicity of an eigenvalue in a matrix whose graph is a treeLinear and Multilinear Algebra, 1999