#### 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.

#### BYU ScholarsArchive Citation

Barrett, Wayne; Van Der Holst, Hein; and Loewy, Raphael, "Graphs Whose Minimal Rank is Two: The Finite Fields Case" (2005). *All Faculty Publications*. 395.

http://scholarsarchive.byu.edu/facpub/395

#### Document Type

Peer-Reviewed Article

#### Publication Date

2005-02-01

#### Permanent URL

http://hdl.lib.byu.edu/1877/1483

#### Publisher

International Linear Algebra Society

#### Language

English

#### College

Physical and Mathematical Sciences

#### Department

Mathematics

#### Copyright Status

© 2005 American Mathematical Society

#### Copyright Use Information

http://lib.byu.edu/about/copyright/