Computational and Theoretical Challenges for Computing the Minimum Rank of a Graph
Research output: Contribution to journal › Journal article › peer-review
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.
|Journal||INFORMS Journal on Computing|
|Publication status||Published - 2022|
© 2022 INFORMS.
- forts, matroid, maximum nullity, minimum rank, zero forcing
Accepted author manuscript