On the sparsity order of a graph and its deficiency in chordality

摘要: Given a graph $G$ on $n$ nodes, let ${cal P_G$ denote the cone consisting of positive semidefinite $ntimes n$ matrices (with real or complex entries) having zero entry at every position corresponding to non edge $G$. Then, order is defined as maximum rank matrix lying an extreme ray P_G$. It shown in [AHMR88] that graphs 1 are precisely chordal and characterization $2$ conjectured there case. We show this paper validity conjecture. Moreover, we characterize with 2 case give decomposition result for $le 2$ both cases. As application, these can be recognized polynomial time. also establish inequality relating ${rm ord_{oF(G)$ ($oF=oR$ $oC$) parameter fill(G)$ minimum number edges needed added obtain graph. Namely, ord_{oF(G)le +epsilon_oF cdot {rm where $epsilon_oR=1$ $epsilon _oC =2$; settles conjecture posed [HPR89].