Let G be a simple graph on n vertices, and let S(G) be the class of all real-valued symmetric nxn matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. The smallest rank achieved by a matrix in S(G) is called the minimum rank of G, denoted mr(G). The maximum nullity achieved by a matrix in S(G) is denoted M(G). For each graph G, there is an associated minimum rank class, MR(G) consisting of all matrices A in S(G) with rank A = mr(G). Although no restrictions are applied to the diagonal entries of matrices in S(G), sometimes diagonal entries corresponding to specific vertices of G must be zero for all matrices in MR(G). These vertices are known as nil vertices (see [6]). In this paper I discuss some basic results about nil vertices in general and nil vertices in cographs and prove that cographs with a nil vertex of a particular form contain two other nil vertices symmetric to the first. I discuss several open questions relating to these results and a counterexample. I prove that for all cographs G without an induced complete tripartite graph with independent sets all of size 3, the zero-forcing number Z(G), a graph theoretic parameter, is equal to M(G). In fact this result holds for a slightly larger class of cographs and in particular holds for all threshold graphs. Lastly, I prove that the maximum of the minimum ranks of all cographs on n vertices is the floor of 2n/3.
| Identifer | oai:union.ndltd.org:BGMYU2/oai:scholarsarchive.byu.edu:etd-4872 |
| Date | 04 December 2013 |
| Creators | Malloy, Nicole Andrea |
| Publisher | BYU ScholarsArchive |
| Source Sets | Brigham Young University |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Theses and Dissertations |
| Rights | http://lib.byu.edu/about/copyright/ |
Page generated in 0.0021 seconds