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.
| Identifer | oai:union.ndltd.org:BGMYU2/oai:scholarsarchive.byu.edu:etd-5401 |
| Date | 01 March 2014 |
| Creators | Sexton, William Nelson |
| Publisher | BYU ScholarsArchive |
| Source Sets | Brigham Young University |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | All Theses and Dissertations |
| Rights | http://lib.byu.edu/about/copyright/ |
Page generated in 0.0022 seconds