Abstract

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.

Degree

PhD

College and Department

Physical and Mathematical Sciences; Mathematics

Rights

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

Date Submitted

2007-07-16

Document Type

Dissertation

Handle

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

Keywords

minimum rank, symmetric matrix, forbidden subgraph, field of two elements, finite field, projective geometry, polarity, rank 3

Included in

Mathematics Commons

Share

COinS