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

DOI10.1287/ijoc.2022.1219OpenAlexW4293215225WikidataQ114058176 ScholiaQ114058176MaRDI QIDQ5060771

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

Publication date: 11 January 2023

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/ijoc.2022.1219

zbMATH Keywords

matroidminimum rankmaximum nullityzero forcingforts

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Related Items (1)

Sparks of symmetric matrices and their graphs

Cites Work

• Unnamed Item
• Extremal values and bounds for the zero forcing number
• Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph
• On the graph complement conjecture for minimum rank
• On the minimum rank of the join of graphs and decomposable graphs
• Forbidden minors for the class of graphs \(G\) with \(\xi (G) \leqslant 2\)
• Orthogonal representations, minimum rank, and graph complements
• On minimum rank and zero forcing sets of a graph
• Techniques for determining the minimum rank of a small graph
• The minimum rank problem over the finite field of order 2: Minimum rank 3
• Lower bounds in minimum rank problems
• A typical vertex of a tree
• Computation of minimal rank and path cover number for certain graphs
• Zero forcing sets and the minimum rank of graphs
• Minimum-rank matrices with prescribed graph
• On the difference between the maximum multiplicity and path cover number for tree-like graphs
• Estimation of the maximum multiplicity of an eigenvalue in terms of the vertex degrees of the graph of a matrix
• The graphs for which the maximum multiplicity of an eigenvalue is two
• Minimum rank of edge subdivisions of graphs
• The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree
• Graphs whose minimal rank is two
• Spectral graph theory and the inverse eigenvalue problem of a graph
• Graphs whose minimal rank is two: The finite fields case
• Parameters Related to Tree‐Width, Zero Forcing, and Maximum Nullity of a Graph
• A variant on the graph parameters of Colin de Verdiere: Implications to the minimum rank of graphs

This page was built for publication: Computational and Theoretical Challenges for Computing the Minimum Rank of a Graph