\documentclass[12pt]{article} \usepackage{e-jc} \specs{P21}{20(4)}{2013} \usepackage{amsthm,amsmath,amssymb} \usepackage{graphicx} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \allowdisplaybreaks \def\re{\par\hang\textindent} \def\ra{\rangle} \def\la{\langle} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{\bf Separability of density matrices of graphs \\ for multipartite systems} \author{Chen Xie \quad Hui Zhao\thanks{Supported by NSFC11101017.} \\ \small College of Applied Sciences\\[-0.8ex] \small Beijing University of Technology\\[-0.8ex] \small Beijing, China\\ \small\tt xiechen11happy@126.com \qquad zhaohui@bjut.edu.cn\\ \and Zhi-Xi Wang\thanks{Supported by KZ201210028032.}\\ \small School of Mathematical Sciences\\[-0.8ex] \small Capital Normal University\\[-0.8ex] \small Beijing, China\\ \small\tt wangzhx@cnu.edu.cn} \date{\dateline{Jan 26, 2013}{Nov 12, 2013}{Nov 22, 2013}\\ \small Mathematics Subject Classifications: 05C90} \begin{document} \maketitle \begin{abstract} We investigate separability of Laplacian matrices of graphs when seen as density matrices. This is a family of quantum states with many combinatorial properties. We firstly show that the well-known matrix realignment criterion can be used to test separability of this type of quantum states. The criterion can be interpreted as novel graph-theoretic idea. Then, we prove that the density matrix of the tensor product of $N$ graphs is $N$-separable. However, the converse is not necessarily true. Additionally, we derive a sufficient condition for $N$-partite entanglement in star graphs and propose a necessary and sufficient condition for separability of nearest point graphs. \bigskip\noindent \textbf{Keywords:} density matrices of graphs, Laplacian matrices; separability \end{abstract} \newpage \section{Introduction} Quantum entanglement is one of the most fascinating features of quantum theory and has numerous applications in quantum information processing, secure communication and channels \cite{1, 2, 3}. The theory of graphs, as a well-developed mathematical area, has many applications in network systems, algorithms, optimization, and other fields \cite{4}. For exploring combinatorial features of entanglement in mixed quantum states, Braunstein et al. \cite{5} introduced a restricted class of states called density matrices of graphs. These states are just normalized graph Laplacians. It follows that study entanglement properties of Laplacians is a combinatorial problem. One of the reasons to study such a topic is that theorems about general sets of quantum states may be more straightforward to prove when restricted to Laplacian matrices. On the other side, graph-theoretic results may be reinterpreted in terms of the language of quantum mechanics. Braunstein et al. \cite{6} described a degree condition to test separability of density matrices of graphs. In \cite{7}, the PPT criterion \cite{8} was proved to be necessary and sufficient for separability in $H^2\otimes H^q$. Further results on the multipartite separability of Laplacians were discussed in \cite{9}. Ref. \cite{10} generalized the study of entanglement properties of mixed density matrices to tripartite states. Ref. \cite{11} analyze in detail the separability and quantitative characteristics of entanglement for Laplacians. However, it is generally known that for the case of mixed bipartite states, no single practical procedure can be guaranteed to detect entanglement, even when we restrict the analysis to Laplacians. It would be important to see if in this specific case there is indeed a method. It is expected that the method would be purely combinatorial. In this paper, we study multipartite entanglement properties. By applying graph-theoretic ideas, we are able to significantly expand our ability to distinguish entangled and separable Laplacians. It is well known that the realignment criterion \cite{12, 13, 14, 15} (also called the cross-norm criterion) is a very strong one. The criterion involves only straightforward matrix manipulations and it is easy to apply. We consider realignment for graphs and obtain a simple, computable necessary criterion for separability. This is done in Section 2. In Section 3, we prove that the density matrix of the tensor product of $N$ graphs is $N$-separable. While this seems to be an obvious statement, it is not immediately clear why the converse should hold. In fact, we can show that if a density matrix is $4$-separable, it does not necessarily mean that it can be written as the tensor product of four graphs. In Section 4, we derive a sufficient condition for the entanglement of star graphs and give a necessary and sufficient condition for the separability of the nearest point graph. Comments and conclusions are given in Section 5. It would be valuable to observe whether the difficulty of detecting entanglement for Laplacians is determined by some graph-theoretic parameter, as in the context of fixed-parameter tractability. We hope that the results of the paper will contribute to diffuse the study of separability criteria for graphs among mathematicians interested in algebraic graph theory and graph products. \section{The Laplacian Matrices of Graphs} Let $G=(V(G),\ E(G))$ be a {\it graph} with a vertex set $V(G)$ and an edge set $E(G)$, where $V(G)=\{v_1,\ v_2,\ \cdots,\ v_n\}$ is a non-empty and finite set of {\it vertices} and $E(G)=\{\{v_i,\ v_j\}:\ v_i,\ v_j\in V\}$ is a non-empty set of unordered {\it edges}. A {\it loop} is an edge of the form $\{v_i,\ v_i\}.$ We assume that $E(G)$ does not contain any loops in the sequel. A graph $G$ is said to be on $n$ vertices if $|V(G)|=n$. The {\it degree} of a vertex $v_i\in V(G)$ is the number of edges adjacent to $v_i$, we denote it as $d_G(v_i)$. \begin{definition} The density matrix of graph $G$ is defined as the matrix \begin{eqnarray} \rho(G)=\frac{1}{d_{G}}L(G), \end{eqnarray} where $d_G=\displaystyle\sum_{i=1}^nd_G(v_i)$ is called the {\it degree sum}. $L(G)$ is the {\it combinatorial Laplacian matrix} of graph $G$ defined as \begin{eqnarray} L(G)=\Delta(G)-M(G), \end{eqnarray} where $\Delta(G)$ is the {\it degree matrix} with the diagonal entry $d_G(v_i)$. $M(G)$ is the {\it adjacency matrix} of graph $G$ with the $ij$-th entry defined as \begin{eqnarray} [M(G)]_{i,j}=\left\{ \begin{array}{ll} 1, & \hbox{if $(v_{i},\ v_{j})\in E(G)$;}\\ 0, & \hbox{if $(v_{i},\ v_{j})\notin E(G)$.} \end{array} \right. \end{eqnarray} Two distinct vertices $v_i$ and $v_j$ are said to be {\it adjacent}, if $\{v_i,\ v_j\}\in E(G)$. If every pair of vertices are adjacent, the graph is {\it complete}. $K_n$ denotes the {\it complete graph} on $n$ vertices. The density matrix of a graph is a uniform mixture of pure density matrices, that is, for a graph $G$ on $n$ vertices $v_1,\ v_2,\ \cdots,\ v_n,$ having $s$ edges $\{v_{i_1},\ v_{j_1}\},\ \{v_{i_2},\ v_{j_2}\},\ \cdots,\ \{v_{i_s},\ v_{j_s}\},$ where $1\leq i_1,\ j_1,\ i_2,\ j_2,\ \cdots,\ i_s,\ j_s\leq n,$ $$\rho(G)=\displaystyle\frac{1}{s}\sum_{k=1}^{s}\rho(H_{i_kj_k}),$$ here $H_{i_kj_k}$ is the factor of $G$ such that $$[M(H_{i_kj_k})]_{u,\ w}=\left\{ \begin{array}{ll} 1, & \hbox{if}\ u=i_k\ \hbox{and}\ w=j_k\ \hbox{or}\ w=i_k\ \hbox{and}\ u=j_k;\\ 0, & \hbox{otherwise.} \end{array} \right.$$ The density matrix $\rho(H_{i_kj_k})$ is {\it pure}. \end{definition} \begin{definition} A {\it star graph} \cite{10} on $n$ vertices $v_1,\ v_2,\ \cdots,\ v_n$ is the graph whose set of edges is $\{\{v_1,\ v_i\}:\ i=2,\ 3,\ \cdots,\ n\}$. \end{definition} \begin{definition} A {\it nearest point graph} \cite{10} is a graph whose vertices are identified with the points of a cuboid and the edges have length 1, $\sqrt{2}$ or $\sqrt{3}. $ \end{definition} \begin{definition} The state $\rho$ acting on $H=H_{1}\otimes H_{2}\otimes\cdots\otimes H_{N}$ is {\it separable} if it can be written as \begin{eqnarray} \rho=\sum_{i}p_{i}\rho_{1}^{i}\otimes \rho_{2}^{i}\otimes\cdots\otimes \rho_{N}^{i}, \end{eqnarray} where $\rho_{j}^{i}$ is the density matrix on $H_{j}$ respectively. Otherwise, the state is {\it entangled}. \end{definition} \begin{definition} The {\it tensor product of graphs} $G_1,\ \ldots,\ G_N$, denoted by $G_1\otimes \cdots\otimes G_N$, is the graph whose adjacency matrix is $M(G_1\otimes \cdots\otimes G_N)=M(G_1)\otimes \cdots\otimes M(G_N).$ \end{definition} \begin{definition} Let $G_j$ be a graph on $m_j$ vertices, $v^j_1,\ v^j_2,\ \cdots,\ v^j_{m_j}$, and $n_j$ edges, $\{v^j_{c^j_1}$,\ $v^j_{d^j_1}\}$,\ $\cdots, \{v^j_{c^j_{n_j}}, v^j_{d^j_{n_j}}\} $ with $1\leq c^j_1,\ d^j_1,\ \cdots,\ c^j_{n_j},\ d^j_{n_j}\leq m_j$, $j=1,2,\cdots, N$. Suppose Hilbert space ${H}_1$ is the space spanned by the orthonormal basis $\{|v^{1}_1\ra,\ |v^{1}_{2}\ra,\ \cdots,\ |v^{1}_{m_1}\ra\}$ associated to $V(G_1)$; $\cdots$; ${H}_N$ is the space spanned by the orthonormal basis $\{|v^{N}_1\ra,$\ $|v^{N}_2\ra,$\ $\cdots,$\ $|v^{N}_{m_N}\ra\}$ associated to $V(G_N)$. The density matrix $\rho(G_1\otimes \cdots\otimes G_N)$ is {\it $N$-separable} with respect to Hilbert space ${H}_1\otimes \cdots\otimes {H}_N$ and any graph $G$ on $n$ vertices is {\it $N$-separable} with respect to space ${C}^{m_1}\otimes \cdots\otimes {C}^{m_N}$, where $n=m_1m_2\cdots m_N$. \end{definition} \begin{definition} For an $m\times n$ matrix $A=[a_{ij}],$ where $a_{ij}$ is the matrix entry of $A$, the vector $vec(A)$ is defined as \begin{eqnarray} vec(A)=[a_{11}, \cdots, a_{m1}, a_{12}, \cdots, a_{m2}, \cdots, a_{1n}, \cdots, a_{mn}]^{T}. \end{eqnarray} Let $Z$ be an $m\times m$ block matrix with block size $n\times n$. The realigned matrix $\widetilde{Z}$ of size $m^2 \times n^2$ is defined as \begin{eqnarray} \widetilde{Z}\equiv\begin{pmatrix} vec(Z_{1,1}^{T})\\ \vdots\\ vec(Z_{m,1}^{T})\\ \vdots\\ vec(Z_{1,m}^{T})\\ \vdots\\ vec(Z_{m,m}^{T}) \end{pmatrix}. \end{eqnarray} \end{definition} If an $m\times n$ bipartite density matrix $\rho_{AB}$ is separable, then for the $m^2\times n^2$ matrix $\widetilde{\rho_{AB}}$ the Ky Fan norm which is the sum of all the singular values of $\widetilde{\rho_{AB}}$ is less than or equal to 1 \cite{14}. Next applying this result, we present a separability criterion. For a $pq\times pq$ matrix $A$, $A_{ij}$ denotes the $(i,j)$-th element of $A$. Let $f$ be the canonical bijection between ${1,\cdots, p}\times {1, \cdots, q}$ and ${1,\cdots, pq}: f(i,j)=(i-1)q+j$. If $f(i_{1},j_{1})=k$ and $f(i_{2},j_{2})=l$, then $A_{kl}$ can be written as $A_{(i_{1},j_{1})(i_{2},j_{2})}$. \begin{theorem} For the graph $G$ with the Laplacian matrix $A=(a_{ij})_{n^{2}\times n^{2}}$, the density matrix of the graph $G$ is entangled if \begin{eqnarray} |\sum_{k=1}^{n}d_{G}(v_{k})-N(k_{1}, k_{2})|>1, \end{eqnarray} for all vertices $v_{k}=f(k,k)=(k-1)n+k$, $k=1 ,\cdots, n$, where $N(k_{1},k_{2})$ is the number of edges between $v_{k_{1}}$ and $v_{k_{2}}$, $v_{k_{1}} \neq v_{k_{2}}$. \end{theorem} \begin{proof} Suppose \begin{eqnarray} A=\begin{pmatrix} a_{1 1}&\cdots&a_{1 n}&\cdots&a_{1 n^{2}-n}&\cdots&a_{1 n^{2}}\\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\ a_{1 n}&\cdots&a_{n n}&\cdots&a_{n n^{2}-n}&\cdots&a_{n n^{2}}\\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\ a_{1 n^{2}-n}&\cdots&a_{n n^{2}-n}&\cdots&a_{n^{2}-n n^{2}-n}&\cdots&a_{n^{2}-n n^{2}}\\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\ a_{1 n^{2}}&\cdots&a_{n n^{2}}&\cdots&a_{n^{2}-n n^{2}}&\cdots&a_{n^{2} n^{2}}\\ \end{pmatrix} \end{eqnarray} is the Laplacian matrix of a graph, and the realigned matrix $\widetilde{A}$ is \begin{eqnarray} \widetilde{A}=\begin{pmatrix} a_{1 1}&\cdots&a_{1 n}&\cdots&a_{1 n}&\cdots&a_{n n}\\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\ a_{1 n^{2}-n}&\cdots&a_{1 n^{2}}&\cdots&a_{n n^{2}-n}&\cdots&a_{n n^{2}}\\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\ a_{1 n^{2}-n}&\cdots&a_{n n^{2}-n}&\cdots&a_{1 n^{2}}&\cdots&a_{n n^{2}}\\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\ a_{n^{2}-n n^{2}-n}&\cdots&a_{n^{2}-n n^{2}}&\cdots&a_{n^{2}-n n^{2}}&\cdots&a_{n^{2} n^{2}}\\ \end{pmatrix}. \end{eqnarray} The diagonal elements of $\widetilde{A}$ are only $N(k_{1}, k_{1})$ or $N(k_{1}, k_{2})$, $k_{1}, k_{2}=1,\cdots, n$. So if $|\sum_{k=1}^{n}d_{G}(v_{k})-N(k_{1}, k_{2})|>1,$ we have $tr(\widetilde{A})>1$, the sum of the eigenvalue of $\widetilde{A}$ is greater than $1$. It is obvious that the sum of the singular values of $\widetilde{A}$ is greater than $1$, therefore the density matrix of the graph $G$ is entangled. \end{proof} \section{Separability of Graphs} In Ref. \cite{10} the entanglement of mixed density matrices for tripartite states was discussed. Now, we generalized their results to multipartite quantum systems. \begin{theorem} The density matrix of the tensor product of $N$ graphs is $N$-separable. \end{theorem} \begin{proof} Using the Definitions 1 and 6, we have $$\rho(G_1)=\frac{1}{n_1} \sum_{p_1=1}^{n_1} \rho(H_{c^{1}_{p_1} d^{1}_{p_1}}^{(1)}), \rho(G_2)=\frac{1}{n_2} \sum_{p_2=1}^{n_2} \rho(H_{c^{2}_{p_2} d^{2}_{p_2}}^{(2)}), \cdots, \rho(G_N)=\frac{1}{n_N} \sum_{p_N=1}^{n_N} \rho(H_{c^{N}_{p_N} d^{N}_{p_N}}^{(N)}).$$ $H^{(i)}$ denote $H_{c^{i}_{p_i} d^{i}_{p_i}}^{(i)}$ with $i=1, \cdots, N$, we have \begin{eqnarray} &&\rho(G_1\otimes G_2\otimes \cdots\otimes G_N) \nonumber \\ &=&\displaystyle\frac{1}{d_{G_1\otimes G_2\otimes \cdots \otimes G_N}}[\Delta(G_1\otimes G_2\otimes\cdots\otimes G_N)-M(G_1\otimes G_2\otimes \cdots \otimes G_N)] \nonumber \\ &=&\displaystyle\frac{1}{2^{N}\cdot n_{1} n_{2} \cdots n_{N}} \sum_{p_1, p_2, \cdots, p_N=1}^{n_{1}, n_{2}, \cdots , n_{N}} [\Delta(H^{(1)}) \otimes \Delta(H^{(2)}) \otimes \cdots \otimes \Delta(H^{(N)}) \nonumber \\ &&-M(H^{(1)}) \otimes M(H^{(2)}) \otimes \cdots \otimes M(H^{(N)})] \nonumber \\ &=&\displaystyle\frac{1}{2^{N-1}\cdot n_{1} n_{2} \cdots n_{N}} \sum_{p_1, p_2, \cdots, p_N=1}^{n_{1}, n_{2}, \cdots ,n_{N}} [\rho(H^{(1)})\otimes \rho_+(H^{(2)})\otimes \cdots\otimes \rho_+(H^{(N)}) \nonumber \\ &&+\rho_+(H^{(1)})\otimes \rho(H^{(2)})\otimes \cdots\otimes \rho_+(H^{(N)})+\cdots +\rho_+(H^{(1)})\otimes \rho_+(H^{(2)})\otimes \cdots\otimes \rho(H^{(N)}) \nonumber \\ &&+\cdots +\rho(H^{(1)})\otimes \rho(H^{2})\otimes \cdots\otimes \rho_+(H^{(N)})], \end{eqnarray} where $\rho_+(H^{(i)})\stackrel{\rm def}{=}\Delta(H^{(i)})-\rho(H^{(i)}) =\frac{1}{2}\big(\Delta(H^{(i)})+M(H^{(i)})\big)$. Let $\rho_+(G_i)=\frac{1}{n_i}\sum_{p_i=1}^{n_i}\rho_+(H_{c_{p_i}^{i} d_{p_i}^{i}}^{(i)})$, $i=1, \cdots, N$, we have \begin{eqnarray} &&\rho(G_1\otimes G_2\otimes \cdots \otimes G_N) \nonumber \\ &=&\displaystyle\frac{1}{2^{N-1} n_{1} n_{2} \cdots n_{N}}[\rho(G_1)\otimes \rho_+(G_2)\otimes \cdots\otimes \rho_+(G_N) +\rho_+(G_1)\otimes \rho(G_2)\otimes \cdots\otimes \rho_+(G_N) \nonumber \\ &&+\cdots+\rho_+(G_1)\otimes \rho_+(G_2)\otimes \cdots\otimes \rho(G_N)+\cdots+\rho(G_1)\otimes \rho(G_2)\otimes \cdots\otimes \rho_+(G_N)]. \end{eqnarray} Therefore $\rho(G)$ is $N$-separable. \end{proof} In order to describe the theorem in detail, we give the following example. \begin{example} The density matrix acting on $H_{1}\otimes H_{2}\otimes H_{3}\otimes H_{4}$ of the tensor of four graphs is $4$-separable. Let $G_i$ be a graph on $m_i$ vertices and $n_i$ edges, $i=1,2,3,4$, and denote $H^{(i)}=H_{c^{i}_{p_i} d^{i}_{p_i}}^{(i)}$, we have \begin{eqnarray} \rho_+(G_1)=\frac{1}{n_1}\sum_{p_1=1}^{n_1}\rho_+(H^{(1)}), \rho_+(G_2)=\frac{1}{n_2}\sum_{p_2=1}^{n_2}\rho_+(H^{(2)}), \nonumber \\ \rho_+(G_3)=\frac{1}{n_3}\sum_{p_3=1}^{n_3}\rho_+(H^{(3)}), \rho_+(G_4)=\frac{1}{n_4}\sum_{p_4=1}^{n_4}\rho_+(H^{(4)}), \end{eqnarray} where $\rho_+(H^{(i)})\stackrel{\rm def}{=}\Delta(H^{(i)})-\rho(H^{(i)}) =\frac{1}{2}\big(\Delta(H^{(i)})+M(H^{(i)})\big)$. Since $\rho_+(H^{(i)})$ are all density matrices, \begin{eqnarray} &&\rho(G_1\otimes G_2\otimes G_3\otimes G_4) \nonumber \\ &=& \displaystyle\frac{1}{8}[\rho_+(G_{1})\otimes \rho_+(G_{2})\otimes \rho_+(G_{3})\otimes \rho(G_{4}) +\rho_+(G_{1})\otimes \rho_+(G_{2})\otimes \rho(G_{3})\otimes \rho_+(G_{4}) \nonumber \\ &&+\rho_+(G_{1})\otimes \rho(G_{2})\otimes \rho_+(G_{3})\otimes \rho_+(G_{4}) +\rho_+(G_{1})\otimes \rho(G_{2})\otimes \rho(G_{3})\otimes \rho(G_{4}) \nonumber \\ &&+\rho(G_{1})\otimes \rho_+(G_{2})\otimes \rho_+(G_{3})\otimes \rho_+(G_{4}) +\rho(G_{1})\otimes \rho_+(G_{2})\otimes \rho(G_{3})\otimes \rho(G_{4}) \nonumber \\ &&+\rho(G_{1})\otimes \rho(G_{2})\otimes \rho_+(G_{3})\otimes \rho(G_{4})+\rho(G_{1})\otimes \rho(G_{2})\otimes \rho(G_{3})\otimes \rho_+(G_{4})]. \end{eqnarray} Therefore $\rho(G)$ is $4$-separable. \end{example} \begin{lemma} For the matrix $\sigma=\frac{1}{5}P[\frac{1}{\sqrt{2}}(|ijkp\ra-|rstq\ra )]+\frac{1}{5}P[\frac{1}{\sqrt{2}}(|ijkq\ra -|rstp\ra )]+\frac{1}{5}P[\frac{1}{\sqrt{2}}(|ijtp\ra -|rskq\ra )]+\frac{1}{5}P[\frac{1}{\sqrt{2}}(|iskp\ra -|rjtq\ra )] +\frac{1}{5}P[\frac{1}{\sqrt{2}}(|rjkp\ra -|istq\ra )]$, the following conlusions hold: (i) It is a density matrix and $4$-separable. (ii) The density matrix of complete graph $\rho(K_n)$ is also $4$-separable. \end{lemma} \begin{proof} (i) Since the project operator is semi-positive, $\sigma$ is semi-positive. Moreover, the computation shows that $tr(\sigma)=1$, so $\sigma$ is a density matrix. Let $$|u^{\pm}\ra=\frac{1}{\sqrt{2}}(|i\ra\pm|r\ra),\ \ |v^{\pm}\ra=\frac{1}{\sqrt{2}}(|j\ra\pm|s\ra),\ \ |w^{\pm}\ra=\frac{1}{\sqrt{2}}(|k\ra\pm|t\ra),\ \ |\varphi^{\pm}\ra=\frac{1}{\sqrt{2}}(|p\ra\pm|q\ra).$$ Then $\sigma$ can be written as the linear combination of tensor products, thus $\sigma$ is $4$-separable. (ii) Since $M(K_n)=J_n-I_n$, where $J_n$ is the $n\times n$ all-ones matrix and $I_n$ is the $n\times n$ identity matrix, whenever there is an edge $\{u_{i}v_{j}w_{k}\varphi_p,\ u_{r}v_{s}w_{t}\varphi_q\}$, there must be entangled edges $\{u_{r}v_{j}w_{k}\varphi_p,\ u_{i}v_{s}w_{t}\varphi_p\},$ $\{u_{i}v_{s}w_{k}\varphi_p,\ u_{r}v_{j}w_{t}\varphi_p\},$ $\{u_{i}v_{j}w_{t}\varphi_p,\ u_{r}v_{s}w_{k}\varphi_p\}$ and $\{u_{i}v_{j}w_{k} \varphi_q,\ u_{r}v_{s}w_{t}\varphi_q\},$ so the density matrix $\rho(K_n)$ is $4$-separable. \end{proof} \begin{theorem} Given a graph $G_1\otimes G_2\otimes G_3\otimes G_4,$ the density matrix $\rho(G_1\otimes G_2\otimes G_3\otimes G_4)$ is $4$-separable. However if a density matrix $\rho(G)$ is $4$-separable, it does not necessarily mean that $G=G_1\otimes G_2 \otimes G_3 \otimes G_4$ for some graphs $G_1,\ G_2 ,\ G_3 ,\ G_4.$ \end{theorem} \begin{proof} The first result follows from Example 10. On the other side, from Lemma 11, the density matrix of the complete graph $\rho(K_n)$ is $4$-separable. Because of the complete graph is not a tensor product of three graphs \cite{10}, it is not a tensor product of four graphs. \end{proof} \section{Separability of Some Special Graphs} In this section, we will derive the results of some special graphs. \begin{theorem} The density matrix of star graphs $\rho(K_{1, n-1})$ is $N$-partite entangled for $n=n_{1}n_{2}\cdots n_{N}\geq 2^{N}.$ \end{theorem} \begin{proof} For a star graph $G=K_{1, n-1}$ on $n=n_{1}\cdots n_{N}$ vertices with orthonormal basis $|\alpha_1\ra,\ |\alpha_2\ra,\ \cdots,\ |\alpha_n\ra,$ we have \begin{eqnarray} \rho(G)=\frac{1}{n-1}\sum_{k=2}^n\rho(H_{1k})= \frac{1}{n-1}\sum_{k=2}^nP[\frac{1}{\sqrt{2}}(|\alpha_1\ra-|\alpha_k\ra)]. \end{eqnarray} Consider $\rho(G)$ in $C^{n_1}_{A_1}\otimes C^{n_2}_{A_2}\otimes\cdots\otimes C^{n_N}_{A_N}$, where $C^{n_i}_{A_i}$ are associated to ${\cal H}_{A_i}$ , $i=1,\cdots,N$ respectively. Let $\{|v_1^i\ra,\ |v_2^i\ra,\ \cdots,\ |v_{n_i}^i\ra\}$ be the orthonormal basis of $C^{n_i}_{A_i}$ respectively. So \begin{eqnarray} \rho(G)=\frac{1}{n-1}\sum_{k=2}^{n}P[\frac{1}{\sqrt{2}}(|v_1^1\cdots v_1^N\ra-|v_{r_k}^1\cdots v_{r_k}^N\ra)], \end{eqnarray} it follows that \begin{eqnarray} &&\rho(G) \nonumber \\ &=&\displaystyle\frac{1}{n-1}\Big\{\sum_{i_1=2}^{n_1}P[\frac{1}{\sqrt{2}}(|v_1^1\ra-|v_{i_1}^1\ra)|v_1^2\cdots v_1^N\ra]+\cdots+\sum_{i_N=2}^{n_N}P[\frac{1}{\sqrt{2}}|v_1^1\cdots v_1^{n-1}\ra(|v_1^N\rangle-v_{i_N}^N\ra)] \nonumber \\ &&+\cdots\cdots+\displaystyle\sum_{i_1,\cdots,i_N=2}^{n_1,\cdots,n_N}P[\frac{1}{\sqrt{2}} (|v_1^1\cdots v_1^N\ra-|v_{i_1}^1\cdots v_{i_N}^N \ra)]\Big\}. \end{eqnarray} Consider the following projectors $P_i=|v_1^i\ra\la v_1^i|+|v_2^i\ra\la v_2^i|$, $i=1,\cdots,N$, then \begin{eqnarray} &&(P_1\otimes\cdots\otimes P_N)\rho(G)(P_1\otimes\cdots\otimes P_N) \nonumber \\ &=&\frac{1}{n-1}\Big\{\frac{n-2^N}{2}P[|v_1^1\cdots v_1^N\ra]+P[\frac{1}{\sqrt{2}}(|v_1^1 v_1^2\cdots v_1^N\ra-|v_2^1 v_1^2\cdots v_1^N\ra)] \nonumber \\ &&+\cdots+P[\frac{1}{\sqrt{2}}(|v_1^1\cdots v_1^{N-1} v_1^N\ra-|v_1^1\cdots v_1^{N-1}v_2^N\ra)] \nonumber \\ &&+\cdots\cdots+P[\frac{1}{\sqrt{2}}(|v_1^1\cdots v_1^N\ra-|v_2^1\cdots v_2^N\ra)]\Big\}. \end{eqnarray} So in the basis$|v_1^1\cdots v_1^N\ra, |v_2^1\cdots v_1^N\ra ,\cdots, |v_2^1\cdots v_2^N\ra$, we get a $2^N\times2^N$ matrix \begin{eqnarray} (P_1\otimes\cdots\otimes P_N)\rho(G)(P_1\otimes\cdots\otimes P_N) =\frac{1}{n-1} \left( \begin{array}{cccccccccccc} \frac{n-1}{2}&-\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}&\cdots&-\frac{1}{2}\\[3mm] -\frac{1}{2}&\frac{1}{2}&0&0&\cdots&0\\[3mm] -\frac{1}{2}&0&\frac{1}{2}&0&\cdots&0\\[3mm] -\frac{1}{2}&0&0&\frac{1}{2}&\cdots&0\\[3mm] \vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\[3mm] -\frac{1}{2}&0&0&0&\cdots&\frac{1}{2}\\[3mm] \end{array} \right). \end{eqnarray} The eigenvalues of the partially transposition of $(P_1\otimes\cdots\otimes P_N)\rho(G)(P_1\otimes\cdots\otimes P_N)$ are $\frac{1}{2(n-1)}$ (with multiplicity $2^N-3$), $\frac{1}{(n-1)}$ and the roots of the polynomial $(n-1)^{2}\lambda^{2}-\frac{(n-1)^{2}}{2}\lambda-\frac{1}{2}$. Here the matrix has a negative eigenvalue, therefore $\rho(G)$ is $N$-partite entangled. \end{proof} Next we give an example about $4$-partite entangled states. \begin{example} For a star graph $G=K_{1,\ n-1}$ on $n=n_1n_2n_3n_4$ vertices, the density matrix $\rho(G)$ is 4-partite entangled. From theorem 13, we can get that the partially transposition of $(P_1\otimes P_2\otimes P_3\otimes P_4)\rho(G)(P_1\otimes P_2\otimes P_3\otimes P_4)$ has negative eigenvalue, so $\rho(G)$ is 4-partite entangled. \end{example} Now, let us consider the nearest point graph. \begin{theorem} Let $G$ be a nearest point graph on $n=n_1 n_2 n_3 n_4$ vertices, then the density matrix $\rho(G)$ is 4-separable in $C^m_A\otimes C^p_B\otimes C^q_C\otimes C^q_D$ if and only if it satisfies the degree condition $\Delta(G)=\Delta(G^{\Gamma_A})=\Delta(G^{\Gamma_B})=\Delta(G^{\Gamma_C})=\Delta(G^{\Gamma_D}).$ \end{theorem} \begin{proof} We first prove that the condition is sufficient. Let $\rho(G)$ be the density matrix of a graph on $n=n_1n_2n_3n_4$ vertices and $\Delta(G)=\Delta(G^{\Gamma_A})=\Delta(G^{\Gamma_B})=\Delta(G^{\Gamma_C})=\Delta(G^{\Gamma_D})$ as the degree condition. The degree condition is equivalent to PPT criterion \cite{16}. If $\rho(G)$ is separable in $C^{n_1}_A\otimes C^{n_2}_B\otimes C^{n_3}_C\otimes C^{n_4}_D$, then $\Delta(G)=\Delta(G^{\Gamma_A})=\Delta(G^{\Gamma_B})=\Delta(G^{\Gamma_C})=\Delta(G^{\Gamma_D}).$ In the following, we prove that for the nearest graphs, the condition is also necessary. Let $G$ be a nearest point graph on $n=n_1 n_2 n_3 n_4$ vertices and $f$ edges. We associate to $G$ the orthonormal basis $\{|\alpha_{l}\ra:l=1,\ 2,\ \cdots,\ n\} =\{|u_{i}\ra\otimes|v_{j}\ra\otimes |w_{k}\ra\otimes |\varphi_{p}\ra:\ i=1,\ \cdots,\ n_1;\ j=1,\cdots,\ n_2;\ k=1,\ \cdots, \ n_3; \ p=1,\ \cdots, \ n_4\},$ where $|u_{i}\ra$ , $|v_{j}\ra$ , $|w_{k}\ra$ and $|\varphi_{p}\ra$ are the orthonormal basis of $C^{n_1}_A$, $C^{n_2}_B$, $C^{n_3}_C$, $C^{n_4}_D$ respectively. Let $i,\ r\in\{1,\ \cdots,\ n_1\},\ j,\ s\in\{1,\ \cdots,\ n_2\},\ k,\ t\in\{1, \ \cdots,\ n_3\},\ p,\ q\in\{1, \ \cdots,\ n_4\}.\ \lambda_{ijkp,\ rstq}\in \{0,\ 1\}$ is defined as \begin{eqnarray} \lambda_{ijkp,\ rstq}=\left\{ \begin{array}{ll} 1, & \hbox { if\ $(u_{i}v_{j}w_{k}\varphi_p,\ u_{r}v_{s}w_{t}\varphi_q)\in E(G);$}\\ 0, & \hbox { if\ $(u_{i}v_{j}w_{k}\varphi_p,\ u_{r}v_{s}w_{t}\varphi_q)\notin E(G),$} \end{array} \right. \end{eqnarray} where $i,\ j,\ k,\ r,\ s,\ t$ satisfy the following $14$ conditions: \begin{itemize} \item $i=r,\ j=s,\ k=t,\ p=q+1;\ \ i=r,\ j=s,\ k=t+1,\ p=q;$ \item $i=r,\ j=s+1,\ k=t,\ p=q;\ \ i=r+1,\ j=s,\ k=t,\ p=q;$ \item $i=r+1,\ j=s+1,\ k=t,\ p=q;\ \ i=r+1,\ j=s,\ k=t+1,\ p=q;$ \item $i=r+1,\ j=s,\ k=t,\ p=q+1;\ \ i=r,\ j=s+1,\ k=t+1,\ p=q;$ \item $i=r,\ j=s+1,\ k=t,\ p=q+1;\ \ i=r,\ j=s,\ k=t+1,\ p=q+1;$ \item $i=r+1,\ j=s+1,\ k=t+1,\ p=q;\ \ i=r+1,\ j=s+1,\ k=t,\ p=q+1;$ \item $i=r+1,\ j=s,\ k=t+1,\ p=q+1;\ \ i=r,\ j=s+1,\ k=t+1,\ p=q+1$. \end{itemize} Let $\rho(G),\ \rho(G^{\Gamma_A}),\ \rho(G^{\Gamma_B}),\ \rho(G^{\Gamma_C})$ and $\rho(G^{\Gamma_D})$ be the density matrices corresponding to the graph $G,\ G^{\Gamma_A},\ G^{\Gamma_B},\ G^{\Gamma_C}$ and $G^{\Gamma_D}$ respectively. Then \begin{eqnarray} \rho(G)=&\frac{1}{2f}(\Delta(G)-M(G)),\ &\rho(G^{\Gamma_{A}})=\frac{1}{2f}(\Delta(G^{\Gamma_{A}})-M(G^{\Gamma_{A}})), \nonumber \\ \rho(G^{\Gamma_{B}})=&\frac{1}{2f}(\Delta(G^{\Gamma_{B}})-M(G^{\Gamma_{B}})),\ & \rho(G^{\Gamma_{C}})=\frac{1}{2f}(\Delta(G^{\Gamma_{C}})-M(G^{\Gamma_{C}})), \nonumber \\ \rho(G^{\Gamma_{D}})=&\frac{1}{2f}(\Delta(G^{\Gamma_{D}})-M(G^{\Gamma_{D}})). \end{eqnarray} Let $G_1$ be the subgraph of $G$ whose edges are all the entangled edges of $G$. An edge $\{u_iv_jw_k,\ u_rv_sw_t\}$ is entangled if $i\neq r,\ j\neq s,\ k\neq t$. Let $G^A_1,\ \ G^B_1,\ \ G^C_1,\ \ G^D_1$ be the subgraph of $G^{\Gamma_A}$, $G^{\Gamma_B}$, $G^{\Gamma_C}$, $G^{\Gamma_D}$ corresponding to all the entangled edges. Obviously, $G^A_1=(G_1)^{\Gamma_A},\ G^B_1=(G_1)^{\Gamma_B},\ G^C_1=(G_1)^{\Gamma_C},\ G^D_1=(G_1)^{\Gamma_D}.$ We have \begin{eqnarray} \rho(G_1)=\frac{1}{f}\sum_{i=1}^{n_{1}}\sum_{j=1}^{n_{2}}\sum_{k=1}^{n_{3}}\sum_{P=1}^{n_{4}}\lambda_{ijkp,\ rstq}P[\frac{1}{\sqrt{2}}(|u_iv_jw_k\varphi_p\ra-|u_rv_sw_t\varphi_q\ra)], \end{eqnarray} where $i,\ j,\ k,\ p;\ r,\ s,\ t,\ q$ must satisfy the 14 conditions. We can get $\rho(G^A_1),\ \rho(G^B_1),\ \rho(G^C_1)$ and $\rho(G^D_1)$ by commuting the index of $u,\ v,\ w$ in the above equation respectively. Also we have \begin{eqnarray} \Delta(G_1)=\frac{1}{2f}\sum_{i=1}^{n_{1}}\sum_{j=1}^{n_{2}}\sum_{k=1}^{n_{3}}\sum_{P=1}^{n_{4}} \lambda_{ijkp,\ rstq}P[|u_iv_jw_k\varphi_p\ra], \end{eqnarray} where $i,\ j,\ k,\ p;\ r,\ s,\ t,\ q$ must satisfy either the 14 conditions. We can get $\Delta(G^A_1),\ \Delta(G^B_1)$, $\Delta(G^C_1)$ and $\Delta(G^D_1)$ by commuting the index of $\lambda$ . Let $G_2,\ G^A_2,\ G^B_2$, $G^C_2$ and $G^D_2$ be the subgraph of $G,\ G^A,\ G^B$ , $G^C$ and $G^D$ containing all the unentangled edges, respectively. It is obvious that $\Delta(G_2)=\Delta(G^{\Gamma_A}_2)=\Delta(G^{\Gamma_B}_2)=\Delta(G^{\Gamma_C}_2)=\Delta(G^{\Gamma_D}_2).$ So $\Delta(G)=\Delta(G^{\Gamma_A})=\Delta(G^{\Gamma_B})=\Delta(G^{\Gamma_C})=\Delta(G^{\Gamma_D})$ if and only if $\Delta(G_1)=\Delta(G^{\Gamma_A}_1)=\Delta(G^{\Gamma_B}_1)=\Delta(G^{\Gamma_C}_1)=\Delta(G^{\Gamma_D}_1).$ The condition implies that \begin{eqnarray} \lambda_{ijkp,\ rstq}=\lambda_{rjkp,\ istq}=\lambda_{iskp,\ rjtq}=\lambda_{ijtp ,\ rskq}=\lambda_{ijkq,\ rstp}, \end{eqnarray} for $i,\ r\in\{1,\ 2,\ \cdots,\ n_1\},\ j,\ s \in\{1,\ 2,\ \cdots,\ n_2\},\ \ k,\ t \in\{1,\ 2,\ \cdots,\ n_3 \,\ \ p,\ q \in\{1,\ 2,\ \cdots,\ n_4 \}.$ The above equations show that whenever there is an entangled edge $\{u_{i}v_{j}w_{k}\varphi_p,\ u_{r}v_{s}w_{t}\varphi_q\}$ in $G$ (here $i\neq r,\ j\neq s,\ k\neq t,\ p\neq q$), there must be the entangled edges $\{u_{r}v_{j}w_{k}\varphi_p,\ u_{i}v_{s}w_{t}\varphi_q\},\ \{u_{i}v_{s}w_{k}\varphi_p,\ u_{r}v_{j}w_{t}\varphi_q\}$, $\{u_{i}v_{j}w_{t}\varphi_p,\ u_{r}v_{s}w_{k}\varphi_q\}$ and $\{u_{i}v_{j}w_{k}\varphi_q,\ u_{r}v_{s}w_{t}\}\varphi_p$ in $G$. Let \begin{eqnarray} &&\rho(i,\ j,\ k,\ p;\ r,\ s,\ t,\ q) \nonumber \\ &=&\frac{1}{4}(P[\frac{1}{\sqrt{2}}(|u_{i}v_{j}w_{k}\varphi_p\ra-|u_{r}v_{s}w_{t}\varphi_q\ra)] +P[\frac{1}{\sqrt{2}}(|u_{r}v_{j}w_{k}\varphi_p\ra-|u_{i}v_{s}w_{t}\varphi_q\ra)] \nonumber \\ &&+P[\frac{1}{\sqrt{2}}(|u_{i}v_{s}w_{k}\varphi_p\ra-|u_{r}v_{j}w_{t}\varphi_q\ra)] +P[\frac{1}{\sqrt{2}}(|u_{i}v_{j}w_{t}\varphi_p\ra-|u_{r}v_{s}w_{k}\varphi_q\ra)]) \nonumber \\ &&+P[\frac{1}{\sqrt{2}}(|u_{i}v_{j}w_{k}\varphi_q\ra-|u_{r}v_{s}w_{t}\varphi_p\ra)]). \end{eqnarray} By Lemma 11, we know that $\rho(i,\ j,\ k,\ p;\ r,\ s,\ t,\ q)$ is 4-separable. By using Theorem 3 in Ref. \cite{6} we can easily get $\rho(G_2)$ is 4-separable. Therefore the density matrix $\rho(G)$ is 4-separable in $C^m_A\otimes C^p_B\otimes C^q_C\otimes C^q_D$ \end{proof} Similarly, the result can be generalized to multipartite systems. \begin{theorem} Let $G$ be a nearest point graph on $n=n_1 n_2 \cdots n_N$ vertices. The density matrix $\rho(G)$ is $N$-separable in $C^m_{A_1}\otimes C^p_{A_2}\otimes \cdots \otimes C^q_{A_N}$ if and only if $\Delta(G)=\Delta(G^{\Gamma_{A_1}})=\Delta(G^{\Gamma_{A_2}})=\cdots=\Delta(G^{\Gamma_{A_N}}).$ \end{theorem} \section{Comments and Conclusions} We have studied the separability of Laplacian matrices of graphs. Using the matrix realignment, a entanglement criterion for graphs has been presented. We have proved that if the density matrix $\rho$ is the tensor product of $N$ graphs, then it is $N$-separable. But if a density matrix is $4$-separable, it can not necessarily be written as tensor product of four graphs. Furthermore, we studied the entanglement of star graphs and nearest point graphs. We proved that the star graph $\rho(K_{1,\ n-1})$ is $N$-partite entangled for $n=n_{1}n_{2}\cdots n_{N}\geq 2^{N}.$ And the density matrix $\rho(G)$ of nearest point graph is 4-separable if and only if it satisfies the degree condition. These results are useful to better understand the physical characteristics and mathematical structures of entangled states. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{Acknowledgements} We greatly appreciate the referees$'$ valuable suggestions for improving the original version of this paper. We also greatly thank Tao Li for her advice. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{thebibliography}{16} \bibitem{1} A. Ekert. \newblock Quantum cryptography based on Bell's theorem. \newblock {\em Phys. Rev. Lett.} 67(6): 661--663, 1991. \bibitem{2}C. H. Bennett and S. J. Wiesner. \newblock Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states. \newblock {\em Phys. Rev. Lett.} 69(20): 2881--2884, 1992. \bibitem{3} C. Bennett, G. Brassard, C. Crepeau, R. Jozsa, A. Peres, and W. K. Wootters. \newblock Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels. \newblock {\em Phys. Rev. Lett.} 70(13): 1895--1899, 1993. \bibitem{4} R. B. Bapat. \newblock {\em Graphs and matrices}. \newblock Hindustan Book Agency, New Delhi, India, 1st Edition, 2011. \bibitem{5} S. L. Braunstein, S. Ghosh, and S. Severini. \newblock The Laplacian of a graph as a density matrix: a basic combinatorial approach to separability of mixed states. \newblock {\em Ann. Combin.} 10(3): 291--317, 2006. \bibitem{6} S. L. Braunstein, S. Ghosh, T. Mansour, S. Severini, and R. C. Wilson. \newblock Some families of density matrices for which separability is easily tested. \newblock {\em Phys. Rev. A} 73(1):012320, 2006. \bibitem{7} C. W. Wu. \newblock Conditions for separability in generalized Laplacian matrices and nonnegative matrices as density matrices. \newblock {\em Phys. Lett. A} 251(1): 18--22, 2006. \bibitem{8} A. Peres. \newblock Separability criterion for density matrices. \newblock {\em Phys. Rev. Lett.} 77(8): 1413--1415, 1996. \bibitem{9} C. W. Wu. \newblock Multipartite separability of Laplacian matrices of graphs. \newblock {\em Electron. J. Combin.} 16(1): 61, 2009. \bibitem{10} Z. Wang and Z. X. Wang. \newblock The tripartite separability of density matrices of graphs. \newblock {\em Electron. J. Combin.} 14: 40, 2007. \bibitem{11} C. W. Wu. \newblock On graphs whose Laplacian matrix's multipartite separability is invariant under graph isomorphism. \newblock {\em Discrete Math.} 310(21): 2811--2814, 2010. \bibitem{12} K. Chen and L. A. Wu. \newblock The generalized partial transposition criterion for separability of multipartite quantum states. \newblock {\em Phys. Lett. A} 306(1): 14--20, 2002. \bibitem{13} K. Chen and L. A. Wu. \newblock A matrix realignment method for recognizing entanglement. \newblock {\em Quant. Inf. Comp.} 3(3): 193--202, 2003. \bibitem{14} O. Rudolph. \newblock A separability criterion for density operators. \newblock {\em J. Phys. A: Math. Gen.} 33(21): 3951, 2000. \bibitem{15} O. Rudolph. \newblock Some properties of the computable cross-norm criterion for separability. \newblock {\em Phys. Rev. A} 67(3): 032312, 2003. \bibitem{16} R. Hildebrand, S. Mancini, and S. Severini. \newblock Combinatorial laplacians and positivity under partial transpose. \newblock {\em Math. Struct. in Comp. Sci.} 18(1): 205--219, 2008. \end{thebibliography} \end{document}