Minimum rank of graphs

Abstract

The minimum rank over a field F of a graph G is the smallest possible rank among all symmetric matrices over F whose ( i , j )th entry ( i ≠ j ) is nonzero whenever ij is an edge in G and is zero otherwise, where zero is the additive identity of F. A universally optimal matrix for a graph G is an integer symmetric matrix A such that every off-diagonal entry of A is 0, 1, or –1 and for all fields F, the rank of A is the minimum rank over F of G which is isomorphic to the graph of A. The fan graph, the book graph, the lotus graph and the hanging bridge graph are introduced and the minimum rank of these graphs over any field are presented. We use universally optimal matrices for these graphs to establish field independence of minimum rank. Examples verifying lack of field independence for some graphs are provided.