ELA, Volume 15, pp. 210-214, July 2006, abstract.
On Minimal Rank over Finite Fields
Guoli Ding and Andrei Kotlov
Let F be a field. Given a simple graph G on n vertices,
its minimal rank (with respect to F) is the minimum rank of
a symmetric n-by-n F-valued matrix whose off-diagonal zeroes
are the same as in the adjacency matrix of G. If F is finite,
then for every k, it is shown that the set of graphs of minimal
rank at most k is characterized by finitely many forbidden
induced subgraphs, each on at most ((|F|^k)/2+1)^2 vertices.
These findings also hold in a more general context.