Campus Units
Mathematics
Document Type
Article
Publication Version
Accepted Manuscript
Publication Date
10-2008
Journal or Book Title
Linear Algebra and its Applications
Volume
429
DOI
10.1016/j.laa.2008.04.038
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.
Rights
This manuscript version is made available under the CCBY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
Copyright Owner
Elsevier Inc.
Copyright Date
2008
Language
en
File Format
application/pdf
Recommended Citation
Berman, Avi; Friedland, Shmuel; Hogben, Leslie; Rothblum, Uriel G.; and Shader, Bryan, "An upper bound for the minimum rank of a graph" (2008). Mathematics Publications. 65.
https://lib.dr.iastate.edu/math_pubs/65
Comments
This is a manuscript of an article from Linear Algebra and its Applications 429 (2008): 1629, doi: 10.1016/j.laa.2008.04.038. Posted with permission.