The Minimum Rank Problem for Outerplanar Graphs.

摘要

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 ≠ j, the aij ≠ 0 if and only if ij ∈ 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) ≥ 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 G1, ..., Gk of G such that the ∪E(G i) = E(G). The rank-sum of a cover C of G is denoted as rsC and is equal to sum mr(Gi). 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.