Computational and Theoretical Challenges for Computing the Minimum Rank of a Graph

Illya V. Hicks (), Boris Brimkov (), Louis Deaett (), Ruth Haas (), Derek Mikesell (), David Roberson () and Logan Smith ()
Additional contact information
Illya V. Hicks: Computational Applied Mathematics & Operations Research Department, Rice University, Houston, Texas 77005
Boris Brimkov: Mathematics and Statistics Department, Slippery Rock University, Slippery Rock, Pennsylvania 16057
Louis Deaett: Mathematics and Statistics Department Quninnipiac University, Hamden, Connecticut 06518
Ruth Haas: Department of Mathematics, University of Hawaii at Monoa, Honolulu, Hawaii 96822
Derek Mikesell: Computational Applied Mathematics and Operations Research Department, Rice University, Houston, Texas 77005
David Roberson: Department of Applied Mathematics and Computer Science, Technical University of Denmark, 2800 Kgs, Lyngby, Denmark; Centre for the Mathematics of Quantum Theory (QMATH), Department of Mathematical Sciences, University of Copenhagen, Copenhagen 2100, Denmark
Logan Smith: Computational Applied Mathematics and Operations Research Department, Rice University, Houston, Texas 77005

INFORMS Journal on Computing, 2022, vol. 34, issue 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: minimum rank; maximum nullity; matroid; zero forcing; forts (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1219 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:6:p:2868-2872

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().