Minimum semidefinite rank of outerplanar graphs and the tree cover number

Francesco Barioli, Shaun M. Fallat, Lon H. Mitchell, Sivaram K. Narayan

Research output: Contribution to journalArticlepeer-review

16 Scopus citations

Abstract

Let G = (V,E) be a multigraph with no loops on the vertex set V = {1, 2,..., n}. Define S+(G) as the set of symmetric positive semidefinite matrices A = [aij] with aij ≠ 0, i ≠ j, if ij ∈ E(G) is a single edge and aij = 0, i ≠ 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 of G. The tree cover number of a multigraph G, denoted T(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 parameter T(G). In particular, they show that for any outerplanar multigraph G, M+(G) = T(G).

Original languageEnglish
Pages (from-to)10-21
Number of pages12
JournalElectronic Journal of Linear Algebra
Volume22
DOIs
StatePublished - 2011

Keywords

  • Maximum multiplicity
  • Minimum rank graph
  • Minimum semidefinite rank
  • Outer- planar graphs
  • Tree cover number

Fingerprint

Dive into the research topics of 'Minimum semidefinite rank of outerplanar graphs and the tree cover number'. Together they form a unique fingerprint.

Cite this