Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4603380 | Linear Algebra and its Applications | 2008 | 10 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory