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

Research output: Contribution to journalJournal articlepeer-review

  • Illya V. Hicks
  • Boris Brimkov
  • Louis Deaett
  • Ruth Haas
  • Derek Mikesell
  • David Roberson
  • Logan Smith

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.

Original languageEnglish
JournalINFORMS Journal on Computing
Issue number6
Pages (from-to)2868-2872
Publication statusPublished - 2022

Bibliographical note

Publisher Copyright:
© 2022 INFORMS.

    Research areas

  • forts, matroid, maximum nullity, minimum rank, zero forcing

ID: 334253415