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.