Faculty Publications

Title

Minimum Semidefinite Rank of Outerplanar Graphs and the Tree Cover Number

SelectedWorks Author Profiles:

Lon Mitchell

Document Type

Article

Publication Date

2011

ISSN

1081-3810

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).

Publisher

International Linear Algebra Society

Share

COinS