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