Given a simple graph G with vertex set V(G)={1,2,...,n} define S(G) to be the set of all real symmetric matrices A such that for all i not equal to j, the ijth entry of A is nonzero if and only if ij is in E(G). The range of the ranks of matrices in S(G) is of interest and can be determined by finding the minimum rank. The minimum rank of a graph, denoted mr(G), is the minimum rank achieved by a matrix in S(G). The maximum nullity of a graph, denoted M(G), is the maximum nullity achieved by a matrix in S(G). Note that mr(G)+M(G)=|V(G)| and so in finding the maximum nullity of a graph, the minimum rank of a graph is also determined. The minimum rank problem for a graph G asks us to determine mr(G) which in general is very difficult. A simple graph is planar if there exists a drawing of G in the plane such that any two line segments representing edges of G intersect only at a point which represents a vertex of G. A planar drawing partitions the rest of the plane into open regions called faces. A graph is outerplanar if there exists a planar drawing of G such that every vertex lies on the outer face. We consider the class of outerplanar graphs and summarize some of the recent results concerning the minimum rank problem for this class. The path cover number of a graph, denoted P(G), is the minimum number of vertex-disjoint paths needed to cover all the vertices of G. We show that for all outerplanar graphs G, P(G)is greater than or equal to M(G). We identify a subclass of outerplanar graphs, called partial 2-paths, for which P(G)=M(G). We give a different characterization for another subset of outerplanar graphs, unicyclic graphs, which determines whether M(G)=P(G) or M(G)=P(G)-1. We give an example of a 2-connected outerplanar graph for which P(G) ≥ M(G).A cover of a graph G is a collection of subgraphs of G such that the union of the edge sets of the subgraphs is equal to the E(G). The rank-sum of a cover C of G is denoted as rs(C) and is equal to the sum of the minimum ranks of the subgraphs in C. We show that for an outerplanar graph G, there exists an edge-disjoint cover of G consisting of cliques, stars, cycles, and double cycles such that the rank-sum of the cover is equal to the minimum rank of G. Using the fact that such a cover exists allows us to show that the minimum rank of a weighted outerplanar graph is equal to the minimum rank of its underlying simple graph.
| Identifer | oai:union.ndltd.org:BGMYU2/oai:scholarsarchive.byu.edu:etd-4721 |
| Date | 05 July 2013 |
| Creators | Sinkovic, John Henry |
| 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.0019 seconds