An upper bound for the minimum rank of a graph

Date
2008-10-01
Authors
Berman, Avi
Friedland, Shmuel
Hogben, Leslie
Hogben, Leslie
Rothblum, Uriel
Shader, Bryan
Journal Title
Journal ISSN
Volume Title
Publisher
Source URI
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
Abstract

For a graph G of order n, the minimum rank of G is defined to be the smallest possible rank over all real symmetric n×n matrices A whose (i,j)th entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. We prove an upper bound for minimum rank in terms of minimum degree of a vertex is valid for many graphs, including all bipartite graphs, and conjecture this bound is true over for all graphs, and prove a related bound for all zero-nonzero patterns of (not necessarily symmetric) matrices. Most of the results are valid for matrices over any infinite field, but need not be true for matrices over finite fields.

Description
<p>This is a manuscript of an article from <em>Linear Algebra and its Applications </em>429 (2008): 1629, doi: <a href="http://dx.doi.org/10.1016/j.laa.2008.04.038" target="_blank">10.1016/j.laa.2008.04.038</a>. Posted with permission.</p>
Keywords
Minimum rank, Maximum nullity, Delta conjecture, Minimum degree, Rank, Graph, Matrix
Citation
Collections