Return to search

The Minimum Rank of Schemes on Graphs

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.

Identiferoai:union.ndltd.org:BGMYU2/oai:scholarsarchive.byu.edu:etd-5401
Date01 March 2014
CreatorsSexton, William Nelson
PublisherBYU ScholarsArchive
Source SetsBrigham Young University
Detected LanguageEnglish
Typetext
Formatapplication/pdf
SourceAll Theses and Dissertations
Rightshttp://lib.byu.edu/about/copyright/

Page generated in 0.0016 seconds