Keywords

Rank 2, Minimum rank, Symmetricma trix, Forbidden subgraph, Bilinear symmetric form, Finite field

Abstract

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 × 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 does not = 2, it is shown that mr(F,G) ≤ 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 2t elements, then mr(F,G) ≤ 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.

Original Publication Citation

Barrett, Wanye, Van Der Holst, Hein, and Loewy, Raphael, Graphs Whose Minimal Rank is Two: The Finite Fields case, Elec. Journal of Linear Algebra (25): Vol. 14 p. 32-42.