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

College and Department

Physical and Mathematical Sciences; Mathematics

Rights

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