TY - JOUR

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

AU - Sinkovic, J.H.

AU - Holst, van der, H.

PY - 2011

Y1 - 2011

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

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

U2 - 10.1016/j.laa.2010.11.013

DO - 10.1016/j.laa.2010.11.013

M3 - Article

VL - 434

SP - 1468

EP - 1474

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

SN - 0024-3795

IS - 6

ER -