Computational and Theoretical Challenges for Computing the Minimum Rank of a Graph
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Standard
Computational and Theoretical Challenges for Computing the Minimum Rank of a Graph. / Hicks, Illya V.; Brimkov, Boris; Deaett, Louis; Haas, Ruth; Mikesell, Derek; Roberson, David; Smith, Logan.
I: INFORMS Journal on Computing, Bind 34, Nr. 6, 2022, s. 2868-2872.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Computational and Theoretical Challenges for Computing the Minimum Rank of a Graph
AU - Hicks, Illya V.
AU - Brimkov, Boris
AU - Deaett, Louis
AU - Haas, Ruth
AU - Mikesell, Derek
AU - Roberson, David
AU - Smith, Logan
N1 - Publisher Copyright: © 2022 INFORMS.
PY - 2022
Y1 - 2022
N2 - 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.
AB - 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.
KW - forts
KW - matroid
KW - maximum nullity
KW - minimum rank
KW - zero forcing
UR - http://www.scopus.com/inward/record.url?scp=85146334801&partnerID=8YFLogxK
U2 - 10.1287/ijoc.2022.1219
DO - 10.1287/ijoc.2022.1219
M3 - Journal article
AN - SCOPUS:85146334801
VL - 34
SP - 2868
EP - 2872
JO - INFORMS Journal on Computing
JF - INFORMS Journal on Computing
SN - 1091-9856
IS - 6
ER -
ID: 334253415