Minimum semidefinite rank of outerplanar graphs and the tree cover number

Abstract

Let G= (V, E) be a multigraph with no loops on the vertex setV={1,2, . . . , n}. DefineS+(G) as the set of symmetric positive semidefinite matricesA= [aij] with aij6= 0,i6=j,ifij∈E(G) is a single edge and aij= 0,i6=j, if ij /∈E(G). Let M+(G) denote the maximum multiplicity of zero as an eigenvalue of A∈S+(G) and mr+(G) =|G|−M+(G) denote the minimum semidefinite rank ofG. The tree cover number of a multigraphG, denotedT(G), is the minimum number of vertex disjoint simple trees occurring as induced subgraphs of G that cover all of the vertices of G. The authors present some results on this new graph parameterT(G). In particular, they show that for any outerplanar multigraphG,M+(G) =T(G).