#### Abstract

Let G be an undirected graph on n vertices and let S(G) be the class of all real-valued symmetric n × n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. Let V = {1, 2, . . . , n} be the vertex set of G. A scheme on G is a function f : V → {0, 1}. Given a scheme f on G, there is an associated class of matrices Sf (G) = {A ∈ S(G)|aii = 0 if and only if f(i) = 0}. A scheme f is said to be constructible if there exists a matrix A ∈ Sf (G) with rank A = min{rank M|M ∈ S(G)}. We explore properties of constructible schemes and give a complete classification of which schemes are constructible for paths and cycles. We also consider schemes on complete graphs and show the existence of a graph for which every possible scheme is constructible.

#### Degree

MS

#### College and Department

Physical and Mathematical Sciences; Mathematics

#### Rights

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

#### BYU ScholarsArchive Citation

Sexton, William Nelson, "The Minimum Rank of Schemes on Graphs" (2014). *All Theses and Dissertations*. 4402.

http://scholarsarchive.byu.edu/etd/4402

#### Date Submitted

2014-03-01

#### Document Type

Thesis

#### Handle

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

#### Keywords

Combinatorial Matrix Theory, Diagonal Entry Restrictions, Graph, Minimum Rank, Scheme, Symmetric, Zero forcing