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

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt

  • 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.

OriginalsprogEngelsk
TidsskriftINFORMS Journal on Computing
Vol/bind34
Udgave nummer6
Sider (fra-til)2868-2872
ISSN1091-9856
DOI
StatusUdgivet - 2022

Bibliografisk note

Funding Information:
History: This “Challenge” paper was invited by the Editor in Chief and based on the topics raised by the author at his plenary address at the 2022 INFORMS Computing Society Conference in Tampa, Florida. Funding: This work was supported by the National Science Foundation [Grant DMS-1720225]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.1219.

Funding Information:
This work was supported by the National Science Foundation [Grant DMS-1720225]. The authors thank Rishiprotim Nag for valuable discussions. This project began at the American Institute of Mathematics (AIM), during the workshop “Zero Forcing and Its Applications.” The authors thank AIM for the opportunity to enjoy its productive atmosphere and the workshop organizers and participants for contributing to that stimulating week of discussion and research.

Publisher Copyright:
© 2022 INFORMS.

Links

ID: 334253415