几类重图的阶为4的图对分解

Multidecompositions of Several Multigraphs for Graph-Pair of Order 4

摘要: 对于某个整数t ≥ 4，如果G和H是K_t的两个边不交的、非同构的、无孤立点的生成子图且满足E(G)∪E(H)=E(K_t)，那么称(G,H)是阶为t的图对。Abueida和Daven得到了P_m,P_n，P_m,C_n，P_m,K_n，C_m,C_n，C_m,K_n，K_m,K_n的阶为4的图对分解存在的充要条件。作为其结果的推广，本文给出λ(P_m,P_n)，λ(P_m,C_n)，λ(P_m,K_n)，λ(C_m,C_n)，λ(C_m,K_n)，λ(K_m,K_n)，λL(Kⁿ)的阶为4的图对分解存在的充要条件。

Abstract: For some integer t ≥ 4, if G and H are edge disjoint, non-isomorphic and non-isolated vertices span-ning subgraphs of K_t such that E(G)∪E(H)=E(K_t) , then we say that is a graph-pair of order t. Abueida and Daven have introduced the necessary and sufficient conditions of the exist-ence of multidecompositions of P_m,P_n，P_m,C_n，P_m,K_n，C_m,C_n，C_m,K_n，K_m,K_n for graph- pair of order 4. As a generalization, we obtain the necessary and sufficient conditions of the exist-ence of multidecompositions of λ(P_m,P_n)，λ(P_m,C_n)，λ(P_m,K_n)，λ(C_m,C_n)，λ(C_m,K_n)，λ(K_m,K_n)，λL(Kⁿ) for graph-pair of order 4.

1. 引言

对于某个整数t ≥ 4，如果G和H是 $K_t$ 的两个边不交的、非同构的、无孤立点的生成子图且满足 $E\left(G\right)\cup E\left(H\right)=E\left(K_t\right)$ ，那么称 $\left(G,H\right)$ 是阶为t的图对。如果 $H_1,H_2,\cdots ,H_l$ 是图G的边不交的子图且 $E\left(G\right)={\cup }_{i=1}^{l}E\left(H_i\right)$ ，则我们说G有 $\{H_1,H_2,\cdots ,H_l\}$ -分解，并且记为 $G=H_1\oplus H_2\oplus \cdots \oplus H_l$ 或 $G={\oplus }_{i=1}^l{H}_i$ 。对于 $1\le i\le l$ ，如果 $H_i\cong H$ ，那么我们说G有H-分解。对于 $1\le i\le l$ ，给定一个阶为t的图对 $\left(S,T\right)$ ，如果 $H_i\cong S$ 或 $H_i\cong T$ 且 $H_1,H_2,\cdots ,H_l$ 中至少存在一个S的复制和T的复制，那么我们说G存在阶为t的图对分解且记为G有 $\left\{S,T\right\}$ -分解。设 $C_n$ 表示n个顶点的圈，记为 $\left(v_1,v_2,\cdots ,v_n\right)$ 。我们把两条点不交的边记为 $E_2$ 。显然在上述定义下，阶为4的图对是 $\left(C_4,E_2\right)$ 。注意到，如果G存在 $\left\{C_4,E_2\right\}$ -分解，那么 $\lambda G$ 存在 $\left\{C_4,E_2\right\}$ -分解。

设G是一个简单图，将G的每条边变成 $\lambda$ 条边得到的重图记为 $\lambda G$ 。简单图G和H的笛卡尔积记为 $G\square H$ ，其中 $V(G\square H)=V\left(G\right)\times V\left(H\right)$ ， $E(G\square H)=\left\{\left(u_1,v_1\right),\left(u_2,v_2\right)\right\}$ $(u_1=u_2,\left\{v_1,v_2\right\}\in E\left(H\right)$ 或 $v_1=v_2,\left\{u_1,u_2\right\}\in E\left(G\right))$ 。显然， $G\square H\cong H\square G$ 。设 $K_n$ 表示n个顶点的完全图，其中 $V\left(K_n\right)={{\rm Z}}_n=\left\{0,1,\cdots ,n-1\right\}$ 。设 $K_{m,n}$ 表示完全二部图 $\left(X,Y\right)$ ，其中 $\left|X\right|=m$ ， $\left|Y\right|=n$ 。尚未给出的图论术语见文献 [1] [2] 。

图分解的存在性问题一直受到众多学者的广泛关注 [3] - [8] 。其中针对阶为t的图对分解的问题，国内外许多学者对其进行了研究与探索并取得了许多结果。2003年，Abueida和Daven [9] 给出了完全图 $K_n$ 的阶为4和5的图对分解的充要条件。作为其结论的推广：2004年，刘萍 [10] 得到了完全多部图 $K_n\left(t\right)$ 的阶为4和5的图对分解的充要条件。2005年，Abueida [11] 等人研究 $\lambda K_n$ 的阶为4和5的图对分解的存在性，给出了 $\lambda K_n$ 的阶为4和5的图对分解的充要条件。2015年，Gao和Roberts [12] 给出了完全图 $K_n$ 的阶为6的图对分解的充要条件。2013年，Abueida和Daven [13] 考虑特殊图的笛卡尔积的阶为4的图对分解的存在性，得到了 $P_m\square P_n$ ， $P_m\square C_n$ ， $P_m\square K_n$ ， $C_m\square C_n$ ， $C_m\square K_n$ ， $K_m\square K_n$ 存在 $\left\{C_4,E_2\right\}$ -分解的充要条件。

受以上文献的启发，本文将给出 $\lambda \left(P_m\square P_n\right)$ ， $\lambda \left(P_m\square C_n\right)$ ， $\lambda \left(P_m\square K_n\right)$ ， $\lambda \left(C_m\square C_n\right)$ ， $\lambda \left(C_m\square K_n\right)$ ， $\lambda \left(K_m\square K_n\right)$ ， $\lambda L\left(K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解的充要条件。因为 $\left|E\left(C_4\right)\right|=4$ ， $\left|E\left(E_2\right)\right|=2$ ，所以G存在 $\left\{C_4,E_2\right\}$ -分解的一个必要条件是 $\left|V\left(G\right)\right|\ge 4$ ， $\left|E\left(G\right)\right|\ge 6$ 且 $\left|E\left(G\right)\right|$ 是偶数。显然，如果图G存在 $C_4$ -分解，那么图G存在 $\left\{C_4,E_2\right\}$ -分解。反过来，如果图G存在 $\left\{C_4,E_2\right\}$ -分解，那么图G不一定存在 $C_4$ -分解。例如： $K_4$ 存在 $\left\{C_4,E_2\right\}$ -分解，但 $K_4$ 不存在 $C_4$ -分解。

2. 预备知识

本节给出了本文需要的一些基本概念和符号。

令图 $G=\left(V\left(G\right),E\left(G\right)\right)$ ，其中 $V\left(G\right)$ 是图G的顶点集， $E\left(G\right)$ 是图G的边集。如果G是一个多重图，那么两个相同端点之间的边视为不同的边。任意非空子集 $S\subseteq V\left(G\right)$ ， $G\left[S\right]$ 表示G的由S导出的子图。G的线图记为 $L\left(G\right)=\left(\left\{e|e\in E\left(G\right)\right\},\left\{\left\{e,f\right\}|\left\{e,f\right\}\subseteq E\left(G\right),\left|e\cap f\right|=1\right\}\right)$ 。

定理2.1 $H\left(i\right)$ ， $G\left(j\right)$ 分别表示 $(G\square H)\left[V\left(i\right)\right]$ 和 $(G\square H)\left[V\left(j\right)\right]$ ，其中 $V\left(i\right)=\left\{i\right\}\times V\left(H\right)$ $\left(i\in V\left(G\right)\right)$ ， $V\left(j\right)=V\left(G\right)\times \left\{j\right\}$ $\left(j\in V\left(H\right)\right)$ 。

定理2.2 $Q_n\left(i\right)$ 表示 $L\left(K_n\right)\left[V\left(i\right)\right]$ ，其中 $V\left(i\right)=\left\{\left\{i,j\right\}|j\in {{\rm Z}}_n-\left\{i\right\}\right\}\left(i\in {{\rm Z}}_n\right)$ 。

定理2.3 [13] $P_m\square P_n$ 存在 $\left\{C_4,E_2\right\}$ -分解当且仅1) $m,n$ 都是偶数且当 $m=2$ 时， $n\ge 4$ ，2) $m,n$ 都是偶数且当 $n=2$ 时， $m\ge 4$ ，或3) $m,n$ 都是奇数且 $m\ge 3$ ， $n\ge 3$ 。

定理2.4 [13] $P_m\square C_{2t}$ 存在 $\left\{C_4,E_2\right\}$ -分解当且仅当 $m\ge 2$ ， $t\ge 2$ 且为整数。

定理2.5 [13] $P_m\square K_n$ 存在 $\left\{C_4,E_2\right\}$ -分解当且仅当1) $m,n$ 都是偶数且当 $m=2$ 时， $n\ge 4$ ，2) $m,n$ 都是偶数且当 $n=2$ 时， $m\ge 4$ ，或3) m为奇数， $n\equiv 0,1\left(\mathrm{mod}4\right)$ 且 $n\ge 4$ 。

定理2.6 [13] $C_m\square K_n$ 存在 $\left\{C_4,E_2\right\}$ -分解当且仅当1) m是偶数， $n\ge 2$ ，或2) m是奇数且 $n\equiv 0,3\left(\mathrm{mod}4\right)$ 。

定理2.7 [13] $K_m\square K_n$ $\left(mn\ge 4\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解当且仅当满足下列条件之一：1) $m\equiv n\equiv 0\left(\mathrm{mod}2\right)$ 且当 $m\left(或n\right)=2$ 时， $n\left(或m\right)=2\ge 4$ ，2) m或n) 是奇数且 $n\left(或m\right)\equiv 0\left(\mathrm{mod}4\right)$ ，3) $m\equiv n\equiv 1\left(\mathrm{mod}4\right)$ 且当 $m\left(或n\right)=1$ 时， $n\left(或m\right)\ne 5$ ，或4) $m\equiv n\equiv 3\left(\mathrm{mod}4\right)$ 。

定理2.8 [11] 如果 $m\ge 4$ ，下列结论是正确的：

1) $K_m$ 存在 $\left\{C_4,E_2\right\}$ -分解当且仅当 $m\equiv 0,1\left(\mathrm{mod}4\right)$ 且 $m\ne 5$ 。

2) 如果 $m\equiv 2,3\left(\mathrm{mod}4\right)$ 且 $\lambda$ 是偶数，那么 $\lambda K_m$ 存在 $\left\{C_4,E_2\right\}$ -分解。

定理2.9 [14] 设 $m,n,\lambda$ 是整数， $m,n\ge 3$ 且 $\lambda \ge 1$ 。 $\lambda K_n$ 存在 $C_m$ -分解当且仅当1) $m\le n$ ，2) $\lambda \left(n-1\right)$ 是偶数且3) $m|\lambda \left(\begin{array}{c}n\\ 2\end{array}\right)$ 。

定理2.10 [15] $\lambda L\left(K_n\right)\left(n\ge 4\right)$ 存在 $C_4$ -分解当且仅当1) n是偶数，2) $n\equiv 1\left(\mathrm{mod}4\right)$ ， $\lambda \equiv 0\left(\mathrm{mod}2\right)$ ，3) $n\equiv 3\left(\mathrm{mod}4\right)$ ， $\lambda \equiv 0\left(\mathrm{mod}4\right)$ ，或4) $n\equiv 1\left(\mathrm{mod}8\right)$ ， $\lambda$ 是奇数。

3. 主要结论及其证明

定理3.1 $\lambda \left(P_m\square P_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解当且仅当1) $mn\ge 4$ ，2) $\lambda \left(2mn-m-n\right)\ge 6$ 且是偶数。

证明 假设 $\lambda \left(P_m\square P_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。因为 $\left|V\left(\lambda \left(P_m\square P_n\right)\right)\right|=mn$ 且 $|E(\lambda (P_m\square P_n))|=\lambda \left(m\left(n-1\right)+n\left(m-1\right)\right)=\lambda \left(2mn-m-n\right)$ ，所以 $mn\ge 4$ ， $\lambda \left(2mn-m-n\right)\ge 6$ 且偶数。因此，必要性得证。

下证充分性。设 $V(\lambda (P_m\square P_n))=Z_m\times Z_n$ 。我们分以下两种情况讨论：

情形1 $m,n$ 奇偶性相同。

当 $m,n$ 同为奇数，由定理2.3，我们有 $\lambda \left(P_m\square P_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。

当 $m,n$ 同为偶数且 $m\ge 4$ 或 $n\ge 4$ ，由定理2.3，我们有 $\lambda \left(P_m\square P_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。

当 $m=n=2$ ，因为 $\lambda \left(2mn-m-n\right)\ge 6$ ，所以 $\lambda \ge 2$ 。对于 $1\le i\le \lambda -1$ ，设 $C\left(1,i\right)=\left(\left(0,0\right),\left(0,1\right),\left(1,1\right),\left(1,0\right)\right)$ ， $E\left(1\right)=\left\{\left(0,0\right),\left(0,1\right)\right\}\cup \left\{\left(1,0\right),\left(1,1\right)\right\}$ ， $E\left(2\right)=\left\{\left(0,0\right),\left(1,0\right)\right\}\cup \left\{\left(0,1\right),\left(1,1\right)\right\}$ 。那么， $\lambda (P_2\square P_2)={\oplus }_{i=1}^{\lambda -1}C\left(1,i\right)\oplus E\left(1\right)\oplus E\left(2\right)$ 。因此， $\lambda (P_2\square P_2)$ 存在 $\left\{C_4,E_2\right\}$ -分解。

情形2 $m,n$ 奇偶性不同。

因为 $\lambda \left(2mn-m-n\right)$ 是偶数，所以 $\lambda$ 是偶数。

对于 $0\le i\le m-2$ ， $0\le j\le n-2$ ，设 $C\left(i,j\right)=\left(\left(i,j\right),\left(i,j+1\right),\left(i+1,j+1\right),\left(i+1,j\right)\right)$ ， $E\left(1,i\right)=\left\{\left(i,0\right),\left(i+1,0\right)\right\}\cup \left\{\left(i,n-1\right),\left(i+1,n-1\right)\right\}$ ， $E\left(2,j\right)=\left\{\left(0,j\right),\left(0,j+1\right)\right\}\cup \{\left(m-1,j\right),(m-1,j+1)\}$ 。那么， $2(P_m\square P_n)={\oplus }_{j=0}^{n-2}\left({\oplus }_{i=0}^{m-2}C\left(i,j\right)\right){\oplus }_{i=0}^{m-2}E\left(1,i\right){\oplus }_{j=0}^{n-2}E\left(2,j\right)$ 。因此， $\lambda \left(P_m\square P_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。

定理3.2 $\lambda \left(P_m\square C_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解当且仅当1) $mn\ge 4$ ，2) $\lambda \left(2mn-n\right)\ge 6$ 且是偶数。

证明 假设 $\lambda \left(P_m\square C_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。因为 $|V(\lambda (P_m\square C_n))|=mn$ 且 $|E(\lambda (P_m\square C_n))|=\lambda \left(mn+n\left(m-1\right)\right)=\lambda \left(2mn-n\right)$ ，所以 $mn\ge 4$ ， $\lambda \left(2mn-n\right)\ge 6$ 且是偶数。因此，必要性得证。

下证充分性。设 $V(\lambda (P_m\square C_n))=Z_m\times Z_n$ 。我们分以下两种情况讨论：

情形1 n是偶数。

由定理2.4， $\lambda \left(P_m\square C_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。

情形2 n是奇数。

因为 $\lambda \left(2mn-n\right)$ 是偶数，所以 $\lambda$ 是偶数。对于 $0\le i\le m-1$ ，设 $E\left(i\right)=\left\{\left(i,0\right),\left(i,n-1\right)\right\}\cup \{(i+1,0),\left(i+1,n-1\right)\}$ 。那么， $2(P_m\square C_n)=2(P_m\square P_n){\oplus }_{i=0}^{m-1}E\left(i\right)$ 。由定理3.1， $\lambda \left(P_m\square C_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。

定理3.3 $\lambda \left(P_m\square K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解当且仅当1) $mn\ge 4$ ，2) $\lambda \left(mn\left(n-1\right)/2+n\left(m-1\right)\right)\ge 6$ 且是偶数，且3) $n\ne 1$ 。

证明 假设 $\lambda \left(P_m\square K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。因为 $|V(\lambda (P_m\square K_n))|=mn$ 且 $|E(\lambda (P_m\square K_n))|=\lambda \left(mn\left(n-1\right)/2+n\left(m-1\right)\right)$ ，所以 $mn\ge 4$ ， $\lambda \left(mn\left(n-1\right)/2+n\left(m-1\right)\right)\ge 6$ 且是偶数。当 $n=1$ 时， $\lambda \left(P_m\square K_n\right)\cong \lambda P_m$ 。由于 $\lambda P_m$ 不存在 $C_4$ ，因此 $\lambda (P_m\square K_1)$ 不存在 $\left\{C_4,E_2\right\}$ -分解。因此，必要性得证。

下证充分性。设 $V(\lambda (P_m\square K_n))=Z_m\times Z_n$ 。当 $n=2$ 时， $\lambda (P_m\square K_2)=\lambda (P_m\square P_2)$ ，由定理3.1，我们有 $\lambda (P_m\square K_2)$ 存在 $\left\{C_4,E_2\right\}$ -分解。当 $n=3$ 时， $\lambda (P_m\square K_3)\cong \lambda (P_m\square C_3)$ ，由定理3.2，我们有 $\lambda (P_m\square K_3)$ 存在 $\left\{C_4,E_2\right\}$ -分解。因此，设 $n\ge 4$ 。我们分以下四种情况讨论：

情形1 $n\equiv 0\left(\mathrm{mod}4\right)$ 。

由定理2.5，我们有 $\lambda \left(P_m\square K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。

情形2 $n\equiv 1\left(\mathrm{mod}4\right)$ 。

当m为奇数，由定理2.5，我们有 $\lambda \left(P_m\square K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。

当m为偶数。因为 $\lambda \left(mn\left(n-1\right)/2+n\left(m-1\right)\right)$ 是偶数，所以 $\lambda$ 是偶数。对于 $0\le i\le m-2$ ， $0\le j\le n-1$ ，设 $E\left(i,j\right)=\left\{\left(i,j\right),\left(i+1,j\right)\right\}\cup \left\{\left(i,j+1\right),\left(i+1,j+1\right)\right\}$ 。 $2\left(P_m\square K_n\right)={\oplus }_{i=0}^{m-1}2K_n\left(i\right){\oplus }_{j=0}^{n-1}\left({\oplus }_{i=0}^{m-2}E\left(i,j\right)\right)$ 。显然， $2K_n\left(i\right)\cong 2K_n$ 。由定理2.8和2.9，我们有 $\lambda \left(P_m\square K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。

情形3 $n\equiv 2\left(\mathrm{mod}4\right)$ 。

当m为偶数，由定理2.5，我们有 $\lambda \left(P_m\square K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。

当m为奇数。因为 $\lambda \left(mn\left(n-1\right)/2+n\left(m-1\right)\right)$ 是偶数，所以 $\lambda$ 是偶数。对于 $0\le i\le m-2$ ， $0\le j\le n-1$ ，设 $E\left(i,j\right)=\left\{\left(i,j\right),\left(i+1,j\right)\right\}\cup \left\{\left(i,j+1\right),\left(i+1,j+1\right)\right\}$ 。 $2\left(P_m\square K_n\right)={\oplus }_{i=0}^{m-1}2K_n\left(i\right){\oplus }_{j=0}^{n-1}\left({\oplus }_{i=0}^{m-2}E\left(i,j\right)\right)$ 。显然， $2K_n\left(i\right)\cong 2K_n$ 。由定理2.8，我们有 $\lambda \left(P_m\square K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。

情形4 $n\equiv 3\left(\mathrm{mod}4\right)$ 。

因为 $\lambda \left(mn\left(n-1\right)/2+n\left(m-1\right)\right)$ 是偶数，所以 $\lambda$ 是偶数。对于 $0\le i\le m-2$ ， $0\le j\le n-1$ ，设 $E\left(i,j\right)=\left\{\left(i,j\right),\left(i+1,j\right)\right\}\cup \left\{\left(i,j+1\right),\left(i+1,j+1\right)\right\}$ 。 $2\left(P_m\square K_n\right)={\oplus }_{i=0}^{m-1}2K_n\left(i\right){\oplus }_{j=0}^{n-1}\left({\oplus }_{i=0}^{m-2}E\left(i,j\right)\right)$ 。显然， $2K_n\left(i\right)\cong 2K_n$ 。由定理2.8，我们有 $\lambda \left(P_m\square K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。

定理 3.4 $\lambda \left(C_m\square K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解当且仅当1) $mn\ge 4$ ，2) $\lambda \left(mn\left(n-1\right)/2+mn\right)\ge 6$ 且是偶数，且3) 当 $n=1$ 时， $m=4$ 。

证明 假设 $\lambda \left(C_m\square K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。因为 $|V(\lambda (C_m\square K_n))|=mn$ 且 $|E(\lambda (C_m\square K_n))|=\lambda \left(mn\left(n-1\right)/2+mn\right)$ ，所以 $mn\ge 4$ ， $\lambda \left(mn\left(n-1\right)/2+mn\right)\ge 6$ 且是偶数。当 $n=1$ 时， $\lambda (C_m\square K_1)\cong \lambda C_m$ 。假设 $m\ne 4$ ，那么 $\lambda C_m$ 不包含 $C_4$ 。因此，必要性得证。

下证充分性。设 $V(\lambda (C_m\square K_n))=Z_m\times Z_n$ 。当 $n=2$ ， $\lambda (C_m\square K_2)\cong \lambda (C_m\square P_2)$ ，由定理3.2，我们有 $\lambda (C_m\square P_2)$ 存在 $\left\{C_4,E_2\right\}$ -分解。因此，设 $n\ne 2$ 。我们分以下两种情况讨论：

情形1 m是偶数。

当 $n\ne 1$ ，由定理2.6，我们有 $\lambda \left(C_m\square K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。

当 $n=1$ 。因为 $\lambda \left(mn\left(n-1\right)/2+mn\right)\ge 6$ ，所以 $\lambda \ge 2$ 。对于 $1\le i\le \lambda -1$ ，设 $C\left(1,i\right)=(\left(0,0\right),\left(1,0\right),\left(2,0\right),\left(3,0\right))$ ， $E\left(1\right)=\left\{\left(0,0\right),\left(1,0\right)\right\}\cup \left\{\left(2,0\right),\left(3,0\right)\right\}$ ， $E\left(2\right)=\left\{\left(1,0\right),\left(2,0\right)\right\}\cup \left\{\left(0,0\right),\left(3,0\right)\right\}$ 。那么， $\lambda (C_4\square K_1)={\oplus }_{i=1}^{\lambda -1}C\left(1,i\right)\oplus E\left(1\right)\oplus E\left(2\right)$ 。因此， $\lambda (C_4\square K_1)$ 存在 $\left\{C_4,E_2\right\}$ -分解。

情形2 m是奇数。

当 $n\equiv 0,3\left(\mathrm{mod}4\right)$ 。由定理2.6，我们有 $\lambda \left(C_m\square K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。

当 $n\equiv 1,2\left(\mathrm{mod}4\right)$ 。因为 $\lambda \left(mn\left(n-1\right)/2+mn\right)$ 是偶数，所以 $\lambda$ 是偶数。对于 $0\le j\le n-1$ ，设 $E\left(j\right)=\left\{\left(0,j\right),\left(m-1,j\right)\right\}\cup \left\{\left(0,j+1\right),\left(m-1,j+1\right)\right\}$ 。那么， $2(C_m\square K_n)=2(P_m\square K_n){\oplus }_{j=0}^{n-1}E\left(j\right)$ 。由定理3.3， $\lambda \left(C_m\square K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。

定理3.5 $\lambda \left(K_m\square K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解当且仅当1) $mn\ge 4$ ，2) $\lambda mn\left(m+n-2\right)/2\ge 6$ 且是偶数，且3) 当 $m\left(或n\right)=1$ ， $n\left(或m\right)=5$ 时， $\lambda >1$ 。

证明 假设 $\lambda \left(K_m\square K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。因为 $|V(\lambda (K_m\square K_n))|=mn$ 且 $|E(\lambda (K_m\square K_n))|=\lambda \left(mn\left(n-1\right)/2+mn\left(m-1\right)/2\right)=\lambda mn\left(m+n-2\right)/2$ ，所以 $mn\ge 4$ ， $\lambda mn\left(m+n-2\right)/2\ge 6$ 且是偶数。当 $m=1$ ， $n=5$ 时， $\lambda (K_1\square K_5)\cong \lambda K_5$ 。由定理2.8， $K_5$ 不存在 $\left\{C_4,E_2\right\}$ -分解。所以，当 $m\left(或n\right)=1$ ， $n\left(或m\right)=5$ 时， $\lambda >1$ 。因此，必要性得证。

下证充分性。设 $V(\lambda (K_m\square K_n))=Z_m\times Z_n$ 。当 $m=2$ 时， $\lambda (K_2\square K_n)\cong \lambda (P_2\square K_n)$ ，由定理3.3， $\lambda (K_2\square K_n)$ 存在 $\left\{C_4,E_2\right\}$ -分解。当 $m=3$ 时， $\lambda (K_3\square K_n)\cong \lambda (C_3\square K_n)$ ，由定理3.4， $\lambda (K_3\square K_n)$ 存在 $\left\{C_4,E_2\right\}$ -分解。当 $m=1$ 时， $\lambda (K_1\square K_n)\cong \lambda K_n$ 。当 $n\ne 5$ 时，由定理2.8， $\lambda (K_1\square K_n)$ 存在 $\left\{C_4,E_2\right\}$ -分解。当 $n=5$ 且 $\lambda$ 是偶数时，由定理2.9，我们有 $\lambda K_5$ 存在 $C_4$ -分解。因为 $C_4=E_2\oplus E_2$ ，所以 $\lambda K_5$ 存在 $\left\{C_4,E_2\right\}$ -分解。当 $n=5$ 且 $\lambda$ 是奇数时，设 $E\left(1\right)=\left\{\left(0,0\right),\left(0,1\right)\right\}\cup \left\{\left(0,2\right),\left(0,4\right)\right\}$ ， $E\left(2\right)=\left\{\left(0,1\right),\left(0,2\right)\right\}\cup \left\{\left(0,3\right),\left(0,4\right)\right\}$ ， $E\left(3\right)=\left\{\left(0,0\right),\left(0,4\right)\right\}\cup \left\{\left(0,2\right),\left(0,3\right)\right\}$ ， $E\left(4\right)=\left\{\left(0,0\right),\left(0,2\right)\right\}\cup \left\{\left(0,1\right),\left(0,3\right)\right\}$ ， $E\left(5\right)=\left\{\left(0,0\right),\left(0,3\right)\right\}\cup \left\{\left(0,1\right),\left(0,4\right)\right\}$ 。那么， $\lambda K_5=\left(\lambda -1\right)K_5\oplus E\left(1\right)\oplus E\left(2\right)\oplus E\left(3\right)\oplus E\left(4\right)\oplus E\left(5\right)$ 。因此， $\lambda K_5$ 存在 $\left\{C_4,E_2\right\}$ -分解。因此，设 $m\ge 4$ ， $n\ge 4$ 。我们分以下三种情况讨论：

情形1 $m,n$ 是偶数。

由定理2.7，我们有 $\lambda \left(K_m\square K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。

情形2 $m,n$ 是奇数。

设 $m\equiv k_1\left(\mathrm{mod}4\right)$ ， $n\equiv k_2\left(\mathrm{mod}4\right)$ 。不失一般性，我们假设 $k_1\le k_2$ 。因为 $m,n$ 是奇数，所以 $m+n-2$ 是偶数。因为 $\lambda mn\left(m+n-2\right)/2$ 是偶数，所以 $\lambda \left(m+n-2\right)/2$ 是偶数。因此， $m,n,\lambda$ 满足：1) $m+n-2\equiv 0\left(\mathrm{mod}4\right)$ ，2) $m+n-2\equiv 2\left(\mathrm{mod}4\right)$ ， $\lambda$ 是偶数。

当 $m+n-2\equiv 0\left(\mathrm{mod}4\right)$ ，即 $m\equiv n\equiv 1\left(\mathrm{mod}4\right)$ 或 $m\equiv n\equiv 3\left(\mathrm{mod}4\right)$ 。由定理2.7，我们有 $\lambda \left(K_m\square K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。

当 $m+n-2\equiv 2\left(\mathrm{mod}4\right)$ ，即 $m\equiv 1\left(\mathrm{mod}4\right)$ ， $n\equiv 3\left(\mathrm{mod}4\right)$ 。

注意到 $\lambda \left(K_m\square K_n\right)={\oplus }_{i=0}^{m-1}\lambda K_n\left(i\right){\oplus }_{j=0}^{n-1}\lambda K_m\left(j\right)$ ， $\lambda K_n\left(i\right)\cong \lambda K_n\left(0\le i\le m-1\right)$ ， $\lambda K_m\left(j\right)\cong \lambda K_m\left(0\le j\le n-1\right)$ 。由定理2.8和2.9，我们有 $\lambda \left(K_m\square K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。

情形3 $m,n$ 是奇偶性不同。

不失一般性，假设m是偶数，n是奇数。

当 $m\equiv 0\left(\mathrm{mod}4\right)$ 。由定理2.7，我们有 $\lambda \left(K_m\square K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。

当 $m\equiv 2\left(\mathrm{mod}4\right)$ 。因为 $\lambda mn\left(m+n-2\right)/2$ 是偶数，所以 $\lambda$ 是偶数。注意到 $\lambda \left(K_m\square K_n\right)={\oplus }_{i=1}^{m-1}\lambda K_n\left(i\right){\oplus }_{j=0}^{n-1}\lambda K_m\left(j\right)$ ， $\lambda K_n\left(i\right)\cong \lambda K_n\left(0\le i\le m-1\right)$ ， $\lambda K_m\left(j\right)\cong \lambda K_m\left(0\le j\le n-1\right)$ 。由定理2.8和2.9，我们有 $\lambda \left(K_m\square K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。

定理3.6 $\lambda L\left(K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解当且仅当1) $n\left(n-1\right)/2\ge 4$ ，2) $\lambda n\left(n-1\right)\left(n-2\right)/2\ge 6$ 且是偶数。

证明 假设 $\lambda L\left(K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。因为 $\left|V\left(\lambda L\left(K_n\right)\right)\right|=n\left(n-1\right)/2$ 且 $\left|E\left(\lambda L\left(K_n\right)\right)\right|=\lambda n\left(n-1\right)\left(n-2\right)/2$ ，所以 $n\left(n-1\right)/2\ge 4$ ， $\lambda n\left(n-1\right)\left(n-2\right)/2\ge 6$ 且是偶数。因此，必要性得证。

下证充分性。设 $V\left(K_n\right)=Z_n$ 。我们分以下三种情况讨论：

情形1 n是偶数。

由定理2.10， $\lambda L\left(K_n\right)$ 存在 $C_4$ -分解，因此 $\lambda L\left(K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。

情形2 $n\equiv 1\left(\mathrm{mod}4\right)$ 。

$\lambda L\left(K_n\right)={\oplus }_{i=0}^{n-1}\lambda Q_n\left(i\right)$ 且 $\lambda Q_n\left(i\right)\cong \lambda K_{n-1}$ 。由定理2.8， $\lambda L\left(K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。

情形3 $n\equiv 3\left(\mathrm{mod}4\right)$ 。

因为 $\lambda n\left(n-1\right)\left(n-2\right)/2$ 是偶数，所以 $\lambda$ 是偶数。 $\lambda L\left(K_n\right)={\oplus }_{i=0}^{n-1}\lambda Q_n\left(i\right)$ 且 $\lambda Q_n\left(i\right)\cong \lambda K_{n-1}$ 。由定理2.8， $\lambda L\left(K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解。

4. 结语

本文给出了 $\lambda \left(P_m\square P_n\right)$ ， $\lambda \left(P_m\square C_n\right)$ ， $\lambda \left(P_m\square K_n\right)$ ， $\lambda \left(C_m\square K_n\right)$ ， $\lambda \left(K_m\square K_n\right)$ ， $\lambda L\left(K_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解的充要条件。在文献 [13] 中， $C_m\square C_n$ 存在 $\left\{C_4,E_2\right\}$ -分解当且仅当 $m\ge 3$ ， $n\ge 3$ 。因此， $\lambda \left(C_m\square C_n\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解的充要条件是 $m\ge 3$ ， $n\ge 3$ 。注意到， $\lambda \left(K_m\square K_n\right)\cong \lambda L\left(K_{m,n}\right)$ ，因此本文也给出了 $\lambda L\left(K_{m,n}\right)$ 存在 $\left\{C_4,E_2\right\}$ -分解的充要条件。

本文仅仅考虑了上述多重图的阶为4的图对分解。在已有的基础上，我们还可以考虑上述图的阶为5或6的图对分解。