ELA, Volume 14, pp. 32-42, February 2005, abstract.
Graphs Whose Minimal Rank is Two: The Finite Fields Case
Wayne Barrett, Hein van der Holst, and Raphael Loewy
Let F be a finite field, G = (V,E) be an undirected graph
on n vertices, and let S(F,G) be the set of all symmetric
n-by-n matrices over F whose nonzero off-diagonal entries
occur in exactly the positions corresponding to the edges
of G. Let mr(F,G) be the minimum rank of all matrices in
S(F,G). If F is a finite field with p^t elements, p is not
equal to 2, it is shown that mr(F,G) is at most 2 if and
only if the complement of G is the join of a complete graph
with either the union of at most (p^t+1)/2 nonempty complete
bipartite graphs or the union of at most two nonempty complete
graphs and of at most (p^t-1)/2 nonempty complete bipartite
graphs. These graphs are also characterized as those for which
9 specific graphs do not occur as induced subgraphs. If F is
a finite field with 2^t elements, then mr(F,G) is at most 2
if and only if the complement of G is the join of a complete
graph with either the union of at most 2^t+1 nonempty complete
graphs or the union of at most one nonempty complete graph
and of at most 2^{t-1} nonempty complete bipartite graphs.
A list of subgraphs that do not occur as induced subgraphs is
provided for this case as well.