We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Computational and Theoretical Challenges for Computing the Minimum Rank of a Graph.
- Authors
Hicks, Illya V.; Brimkov, Boris; Deaett, Louis; Haas, Ruth; Mikesell, Derek; Roberson, David; Smith, Logan
- 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. 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.
- Subjects
TAMPA (Fla.); NATIONAL Science Foundation (U.S.); MATROIDS; SYMMETRIC matrices
- Publication
INFORMS Journal on Computing, 2022, Vol 34, Issue 6, p2868
- ISSN
1091-9856
- Publication type
Article
- DOI
10.1287/ijoc.2022.1219