We have two main results. Our first main result is a sharp bound for the number of vertices in a minimal forbidden subgraph for the graphs having minimum rank at most 3 over the finite field of order 2. We also list all 62 such minimal forbidden subgraphs and show that many of these are minimal forbidden subgraphs for any field. Our second main result is a structural characterization of all graphs having minimum rank at most k for any k over any finite field. This characterization leads to a very strong connection to projective geometry and we apply projective geometry results to the minimum rank problem.
College and Department
Physical and Mathematical Sciences; Mathematics
BYU ScholarsArchive Citation
Grout, Jason Nicholas, "The Minimum Rank Problem Over Finite Fields" (2007). All Theses and Dissertations. 982.
minimum rank, symmetric matrix, forbidden subgraph, field of two elements, finite field, projective geometry, polarity, rank 3