The minimum semidefinite rank of the complement of partial k-trees

J.H. Sinkovic, H. Holst, van der

Research output: Contribution to journalArticleAcademicpeer-review

9 Citations (Scopus)

Abstract

For a graph G=(V,E) with V={1,…,n}, let S(G) be the set of all real symmetric n×n matrices A=[ai,j] with ai,j¿0, i¿j if and only if ijE. We prove the following results. If G is the complement of a partial k-tree H, then there exists a positive semidefinite matrix AS(G) with rank(A)=k+2. If, in addition, k=3 or G is k-connected, then there exist positive semidefinite matrices AS(G) and BS(H) such that rank(A)+rank(B)=n+2.
Original languageEnglish
Pages (from-to)1468-1474
JournalLinear Algebra and Its Applications
Volume434
Issue number6
DOIs
Publication statusPublished - 2011

Fingerprint

Dive into the research topics of 'The minimum semidefinite rank of the complement of partial k-trees'. Together they form a unique fingerprint.

Cite this