On the sparsity order of a graph and its deficiency in chordality (Q1603236): Difference between revisions

For a graph \(G\) on \(n\) vertices \({\mathcal P}_G\) is the cone of \(n\times n\) positive semidefinite matrices with real or complex entries having a zero entry at every off-diagonal position corresponding to a non-edge in \(G\). The sparsity order of \(G\) is the maximum rank of a matrix lying on an extreme ray of the cone \({\mathcal P}_G\). The characterization of the graphs with sparsity order \(1\) was given earlier and the characterization of the graphs with sparsity order \(2\) was conjectured in the same paper. The main result of this paper is the proof of this conjecure.