An upper bound for the minimum rank of a graph

By A. Berman, Shmuel Friedland, Leslie Hogben, U. Rothblum, Bryan L. Shader. 2008

65 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/9edae1503040cff3deff8bf89e31e46ecd198f19

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

In Electrical and Electronic Engineering

Citations in the corpus

On the minimum rank of not necessarily symmetric matrices : a preliminary study (2009, background): “In [3] it was conjectured that for any graph G and any infinite field F , δ(G) ≤ M (G).”