  Density matrices of graphs are combinatorial laplacians normalized to have
trace one (Braunstein \emph{et al.} \emph{Phys. Rev. A,} \textbf{73}:1, 012320
(2006)). If the vertices of a graph are arranged as an array, then its density
matrix carries a block structure with respect to which properties such as
separability can be considered. We prove that the so-called degree-criterion,
which was conjectured to be necessary and sufficient for separability of
density matrices of graphs, is equivalent to the PPT-criterion. As such it is
not sufficient for testing the separability of density matrices of graphs (we
provide an explicit example). Nonetheless, we prove the sufficiency when one of
the array dimensions has length two (for an alternative proof see Wu,
\emph{Phys. Lett. A}\textbf{351} (2006), no. 1-2, 18--22).
  Finally we derive a rational upper bound on the concurrence of density
matrices of graphs and show that this bound is exact for graphs on four
vertices.
