ELA, Volume 11, pp. 258-280, November 2004, abstract.

Graphs Whose Minimal Rank is Two

Wayne Barrett, Hein van der Holst, and Raphael Loewy

Let F be a 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 whose nonzero off-diagonal entries occur 
in exactly the positions corresponding to the edges of G.  
For example, if G is a path, S(F,G) consists of the 
symmetric irreducible tridiagonal matrices. Let mr(F,G) 
be the minimum rank over all matrices in S(F,G). Then 
mr(F,G) = 1 if and only if G is the union of a clique 
with at least 2 vertices and an independent set. If F 
is an infinite field such that char F is not equal to 2, 
then mr(F,G) is at most 2 if and only if the complement 
of G is the join of a clique and a graph that is the union 
of at most two cliques and any number of complete bipartite 
graphs. A similar result is obtained in the case that F is 
an infinite field with char F = 2.  Furthermore, in each 
case, such graphs are characterized as those for which 6 
specific graphs do not occur as induced subgraphs. The 
number of forbidden subgraphs is reduced to 4 if the graph 
is connected. Finally, similar criteria is obtained for the 
minimum rank of a Hermitian matrix to be less than or equal 
to two.  The complement is the join of a clique and a graph 
that is the union of any number of cliques and any number of 
complete bipartite graphs. The number of forbidden subgraphs 
is now 5, or in the connected case, 3.