完全二部多重图的K_2,4-因子分解

K_2,4-Factorization of Complete Bipartite Multigraphs

摘要: 如果完全二部多重图λK_m,n的边集可以划分为λK_m,n的K_p,q-因子，则称λK_m,n存在K_p,q-因子分解。当p = 1、q = 2和p = 2、q = 3时，λK_m,n的K_p,q-因子分解的存在性问题已被完全解决。当p = 1、q = 3和p = 1、q = 4时，K_m,n的K_p,q-因子分解的存在性问题已被基本解决。文章研究当p = 2和q = 4时完全二部多重图λK_m,n的K_2,4-因子分解的存在性。证明完全二部多重图λK_m,n存在K_2,4-因子分解的充分必要条件是：1) m≡n≡0 (mod 2)，2) m ≤ 2n，3) n ≤ 2m，4)，m+n≡0 (mod 6)，5) 3λm,n/[4（m+n）]是整数。

Abstract: Let λK_m,n be a complete bipartite multigraph with two partite sets having m and n vertices, re-spectively. A K_p,q -factorization λK_m,n is a set of edge-disjoint K_p,q -factors of λK_m,n . When p = 1, q = 2 and p = 2, q = 3, the K_p,q -factorization of λK_m,n has been completely solved. When p = 1, q = 3 and p = 1, q = 4, the K_p,q -factorization of K_m,n has been totally solved. In this article, the K_2,4-factorization of λK_m,n is researched. We will give a necessary and sufficient condition for K_2,4-factorization of λK_m,n, that is: 1) m≡n≡0 (mod 2), 2) m ≤ 2n, 3) n ≤ 2m, 4) m+n≡0 (mod 6), 5) 3λm,n/[4(m+n)] .

1. 引言

K_m,n表示完全二部图，其两个部分点集Ｘ和Ｙ分别具有m和n个点。lK_m,n表示完全二部多重图，它是l个两两不交的同构于K_m,n的图的并。如果lK_m,n的一个子图F包含了lK_m,n的所有点，则称Ｆ为lK_m,n的一个支撑子图。若lK_m,n的支撑子图F的每个分支均同构于图K_p,q，则称F为lK_m,n的一个K_p,q-因子。如果lK_m,n的边集可以划分为lK_m,n的K_p,q-因子，则称lK_m,n存在K_p,q-因子分解。在综述文章 [1] 中，Ushio称lK_m,n的K_p,q-因子分解为可分解的(m, n, k, l)二部K_p,q-设计。如果lK_m,n存在K_p,q-因子分解，则称lK_m,n是可K_p,q-因子分解的。本文用到的图论方面的名词术语，均参照图论著作 [2] 。

lK_m,n的K_p,q-因子分解有许多应用，特别是Yamamoto和Ushio等 [3] 用其建立了计算机数据存储的HUBMFS₂方案。当p = 1和q = 2时，Ushio [4] 、Wang和Du [5] 完全解决了lK_m,n的K_1,2-因子分解的存在性问题。Martin在论文 [6] [7] 中分别解决了当p = 1、q = 3与p = 1、q = 4时K_m,n的K_p,q-因子分解的存在性。当p = 2和q = 3时，Wang和Du [8] 完全解决了l = 1时K_m,n的K_2,3-因子分解的存在性。我们在论文 [9] 中完全解决了l > 1时lK_m,n的K_2,3-因子分解的存在性。本文研究当p = 2和q = 4时，完全二部多重图lK_m,n的K_2,4-因子分解的存在性。即我们将证明lK_m,n存在K_2,4-因子分解的充分必要条件。

定理1.1：完全二部多重图lK_m,n存在K_2,4-因子分解的充分必要条件是：1) $m\equiv n\equiv 0$ (mod 2)，2) m £ 2n，3) n £ 2m，4) $m+n\equiv 0$ (mod 6)，5) $3\lambda mn/\left[4\left(m+n\right)\right]$ 是整数。

2. 定理1.1的证明

定理1.1的必要性证明通过简单计算即可得到，充分性部分的证明由以下几个引理构成，第一个引理是显然的，其中 $\gcd \left(x,y\right)$ 表示x和y的最大公约数。

引理2.1：设u，v，x和y是正整数。如果 $\gcd \left(ux,vy\right)=1$，则 $\gcd \left(uv,ux+vy\right)=1$。

引理2.2：设s是任意正整数。如果lK_m,n存在K_2,4-因子分解，则lsK_m,n存在K_2,4-因子分解。

证明：重复lK_m,n的K_2,4-因子分解s次即得lsK_m,n的K_2,4-因子分解。

引理2.3：设s是任意正整数。如果lK_m,n存在K_2,4-因子分解，则lK_ms,ns存在K_2,4-因子分解。

证明：由于K_s,s是可1-因子分解的(参见 [2] )，可设 $\left\{F_i:1\le i\le s\right\}$ 是它的一个1-因子分解。对于每一个1 £ i £ s，用lK_m,n代替F_i的每条边，即得到lK_ms,ns的一个支撑子图G_i，且 $G_i\left(1\le i\le s\right)$ 边集的并为lK_ms,ns。由于lK_m,n是可K_2,4-因子分解的，因而G_i也是可K_2,4-因子分解的。所以lK_ms,ns存在K_2,4-因子分解。

由引理2.3我们易得当m = 2n或n = 2m时，lK_m,n存在K_2,4-因子分解。因此下面我们只需考虑m < 2n且n < 2m时的情形。在这种情形下，我们令 $a=\left(2n-m\right)/6$， $b=\left(2m-n\right)/6$， $t=\left(m+n\right)/6$ 和 $r=3\lambda mn/\left[4\left(m+n\right)\right]$。由定理1.1的条件(1)~(4)可知a，b，t，r是整数，且0 < a < m，0 < b < n。于是有2a + 4b = m，4a + 2b = n。进而可得 $r=\lambda \left(a+b\right)+\lambda ab/\left[\text{2}\left(a+b\right)\right]$。设 $z=\lambda ab/\left[\text{2}\left(a+b\right)\right]$，它也是整数。设 $\gcd \left(2a,4b\right)=d$，2a = dp，4b = dq，其中 $\gcd \left(p,q\right)=1$。因此 $z=\lambda dpq/\left[4\left(2p+q\right)\right]$。于是我们可得下列各式：

$d=4\left(2p+q\right)z/\left(\lambda pq\right)$

$m=4\left(p+q\right)\left(\text{2}p+q\right)z/\left(\lambda pq\right)$

$n=2\left(\text{4}p+q\right)\left(\text{2}p+q\right)z/\left(\lambda pq\right)$

$r=\left(p+q\right)\left(4p+q\right)z/\left(\lambda pq\right)$

$a=\text{2}p\left(\text{2}p+q\right)z/\left(\lambda pq\right)$

$b=q\left(\text{2}p+q\right)z/\left(\lambda pq\right)$

则有以下引理

引理2.4：1) 如果 $\gcd \left(p,4\right)=1$， $\gcd \left(q,16\right)=1$，设 $\gcd \left(2p+q,l\right)=\gamma$，则

$d=\text{4}\left(\text{2}p+q\right)s/\gamma ,m=\text{4}\left(p+q\right)\left(\text{2}p+q\right)s/\gamma ,n=\text{2}\left(\text{4}p+q\right)\left(\text{2}p+q\right)s/\gamma$，

$r=\left(p+q\right)\left(\text{4}p+q\right)s\lambda /\gamma ,a=\text{2}p\left(\text{2}p+q\right)s/\gamma ,b=q\left(\text{2}p+q\right)s/\gamma$

其中s是正整数。

2) 如果， $\gcd \left(q,16\right)=1$，设 $q=\text{2}{q}_{\text{1}}$，设 $\gcd \left(2\left(p+q_1\right),\lambda \right)=\gamma$，则

$d=\text{4}\left(p+q_{\text{1}}\right)s/\gamma ,m=\text{4}\left(p+\text{2}{q}_{\text{1}}\right)\left(p+q_{\text{1}}\right)s/\gamma ,n=\text{4}\left(\text{2}p+q_{\text{1}}\right)\left(p+q_{\text{1}}\right)s/\gamma$，

$r=\left(p+\text{2}{q}_{\text{1}}\right)\left(\text{2}p+q_{\text{1}}\right)s\lambda /\gamma ,a=\text{2}p\left(p+q_{\text{1}}\right)s/\gamma ,b=\text{2}{q}_{\text{1}}\left(p+q_{\text{1}}\right)s/\gamma$

其中s是正整数。

3) 如果 $\gcd \left(p,4\right)=1$， $\gcd \left(q,16\right)=\text{4}$，设 $q=4q_2$，设 $\gcd \left(p+2q_2,l\right)=\gamma$，则

$d=\text{2}\left(p+\text{2}{q}_{\text{2}}\right)s/\gamma ,m=\text{2}\left(p+\text{4}{q}_{\text{2}}\right)\left(p+\text{2}{q}_{\text{2}}\right)s/\gamma ,n=\text{4}\left(p+q_{\text{2}}\right)\left(p+\text{2}{q}_{\text{2}}\right)s/\gamma$，

$r=\left(p+\text{4}{q}_{\text{2}}\right)\left(p+q_{\text{2}}\right)s\lambda /\gamma ,a=p\left(p+\text{2}{q}_{\text{2}}\right)s/\gamma ,b=\text{2}{q}_{\text{2}}\left(p+\text{2}{q}_{\text{2}}\right)s/\gamma$

其中s是正整数。

4) 如果 $\gcd \left(p,4\right)=1$， $\gcd \left(q,16\right)=8$，设 $q=8q_3$，设 $\gcd \left(p+4q_3,\lambda \right)=\gamma$，则

$d=\text{2}\left(p+\text{4}{q}_{\text{3}}\right)s/\gamma ,m=\text{2}\left(p+\text{8}{q}_{\text{3}}\right)\left(p+\text{4}{q}_{\text{3}}\right)s/\gamma ,n=\text{4}\left(p+\text{2}{q}_{\text{3}}\right)\left(p+\text{4}{q}_{\text{3}}\right)s/\gamma$，

$r=\left(p+\text{8}{q}_{\text{3}}\right)\left(p+\text{2}{q}_{\text{3}}\right)s\lambda /\gamma ,a=p\left(p+\text{4}{q}_{\text{3}}\right)s/\gamma ,b=\text{4}{q}_{\text{3}}\left(p+\text{4}{q}_{\text{3}}\right)s/\gamma$

其中s是正整数。

5) 如果 $\gcd \left(p,4\right)=1$， $\gcd \left(q,16\right)=16$，设 $q=16q_4$，设 $\gcd \left(p+8q_4,\lambda \right)=\gamma$，则

$d=\text{2}\left(p+\text{4}{q}_{\text{4}}\right)s/\gamma ,m=\text{2}\left(p+\text{16}{q}_{\text{4}}\right)\left(p+\text{8}{q}_{\text{4}}\right)s/\gamma ,n=\text{4}\left(p+\text{4}{q}_{\text{4}}\right)\left(p+\text{8}{q}_{\text{4}}\right)s/\gamma$，

$r=\left(p+\text{16}{q}_{\text{4}}\right)\left(p+\text{4}{q}_{\text{4}}\right)s\lambda /\gamma ,a=p\left(p+\text{8}{q}_{\text{4}}\right)s/\gamma ,b=\text{8}{q}_{\text{4}}\left(p+\text{8}{q}_{\text{4}}\right)s/\gamma$

其中s是正整数。

6) 如果 $\text{gcd}\left(p,\text{4}\right)=\text{2}$， $\text{gcd}\left(q,\text{16}\right)=\text{1}$，设 $p=2p_1$，设 $\gcd \left(4p_1+q,\lambda \right)=\gamma$，则

$d=4\left(4p_1+q\right)s/\gamma ,m=4\left(2p_1+q\right)\left(4p_1+q\right)s/\gamma ,n=2\left(8p_1+q\right)\left(4p_1+q\right)s/\gamma$，

$r=\left(2p_1+q\right)\left(8p_1+q\right)s\lambda /\gamma ,a=4p_1\left(4p_1+q\right)s/\gamma ,b=q\left(4p_1+q\right)s/\gamma$

其中s是正整数。

7) 如果 $\gcd \left(p,4\right)=4$， $\gcd \left(q,16\right)=1$，设 $p=4p_2$，设 $\gcd \left(8p_2+q,\lambda \right)=\gamma$，则

$d=4\left(8p_2+q\right)s/\gamma ,m=4\left(4p_2+q\right)\left(8p_2+q\right)s/\gamma ,n=2\left(16p_2+q\right)\left(8p_2+q\right)s/\gamma$，

$r=\left(4p_2+q\right)\left(16p_2+q\right)s\lambda /\gamma ,a=8p_2\left(8p_2+q\right)s/\gamma ,b=q\left(8p_2+q\right)s/\gamma$

其中s是正整数。

证明：1) 由条件我们有 $\gcd \left(p,4\right)=\gcd \left(q,16\right)=\gcd \left(p,q\right)=1$，因此 $\gcd \left(4p,q\right)=1$。此时 $r=\left(p+q\right)\left(4p+q\right)z/\left(pq\right)$。根据引理2.1，我们有 $\gcd \left(pq,p+q\right)=\gcd \left(pq,4p+q\right)=1$。所以 $z/\left(pq\right)$ 是正整数。令 $z^{\prime }=z/\left(pq\right)$。设 $\gcd \left(2p\left(2p+q\right),\lambda \right)={\gamma }_1$， $\gcd \left(q\left(2p+q\right),\lambda \right)={\gamma }_2$。由 $a=2p\left(2p+q\right)z^{\prime }/\lambda$， $b=q\left(2p+q\right)z^{\prime }/\lambda$。我们知 $z^{\prime }{\gamma }_1/\lambda$ 和 $z^{\prime }{\gamma }_2/\lambda$ 是正整数。因为，所以 $z^{\prime }\gamma /\lambda$ 是正整数，这里 $\gcd \left(2p+q,\lambda \right)=\gamma$。令 $s=z^{\prime }\gamma /\lambda$，即得(1)中的等式。

(2)~(7)中各式的证明类似于(1)。

引理2.5：对于任意正整数γ，p和q，如果 $m=4\left(p+q\right)\left(2p+q\right)/\gamma$， $n=2\left(4p+q\right)\left(2p+q\right)/\gamma$，则当 $\left(2p+q\right)/\gamma$ 是正整数时，γK_m,n存在K_2,4-因子分解。

证明：记 $a=2p\left(2p+q\right)/\gamma$， $b=q\left(2p+q\right)/\gamma$， $r=\left(p+q\right)\left(4p+q\right)$， $r_{１}=p+q$ 和 $r_2=4p+q$。并令Ｘ和Y是γK_m,n两个部分点集

$X=\left\{x_{i,j}|1\le i\le r_1,1\le j\le 4\left(2p+q\right)/\gamma \right\}$，

$Y=\left\{y_{i,j}|1\le i\le r_2,1\le j\le 2\left(2p+q\right)/\gamma \right\}$。

我们将构作γK_m,n的一个K_2,4-因子分解。我们约定x_i,j和y_i,j的第一个下标分别在和 $\left\{1,2,\cdots ,r_2\right\}$ 中进行模r₁和模r₂的运算，它们的第二个下标分别在 $\left\{\text{1,2,}\cdots \text{,4}\left(2p+q\right)/\gamma \right\}$ 和 { $\left\{\text{1,2,}\cdots \text{,2}\left(2p+q\right)/\gamma \right\}$ 中进行模 $\text{4}\left(2p+q\right)/\gamma$ 和模的运算。

对于每一个正整数i，x，y，z，1 £ I £ p，0 £ x £ 1和0 £ y £ 3，令 $f\left(x\right)=2\left(2p+q\right)x/\gamma$， $g\left(i,y\right)=4\left(i-1\right)+y+1$， $h\left(i,y\right)=4\left(i-1\right)+y$ 并构作如下边集

$E_i=\left\{x_i{}_{,f\left(x\right)+j}{y}_g{}_{\left(i,y\right),h\left(i,y\right)+j}:1\le j\le 2\left(2p+q\right)/\gamma ,0\le x\le 1,0\le y\le 3\right\}$。

对于每一个正整数i，x，y，z，1 £ i £ q和0 £ x，y，z £ 1，令 $u\left(x,y\right)=\left(2p+q\right)\left(2x+y\right)/\gamma$， $v\left(i,y,z\right)=4p+2\left(i-1\right)+\left(2p+q\right)y/\gamma +z$ 并构作如下边集

$E_p{}_{+i}=\left\{x_p{}_{+i,u\left(x,y\right)+j}{y}_{4p}{}_{+i,v\left(i,y,z\right)+j}:1\le j\le 2\left(2p+q\right)/\gamma ,0\le x,y,z\le 1\right\}$。

令 $F={\cup }_{1\le i\le p+q}{E}_i$，则图F就是γK_m,n的一个K_2,4-因子。定义 $X\cup Y$ 到 $X\cup Y$ 上的双射 $\sigma :\sigma \left(x_{i,j}\right)=x_i{}_{+1,j}$， $\sigma \left(y_{i,j}\right)=y_i{}_{+1,j}$。对于每一个 $i\in \left\{\text{1,2,}\cdots \text{,}{r}_{\text{1}}\right\}$ 和每一个 $j\in \left\{\text{1,2,}\cdots \text{,}{r}_2\right\}$，令

$F_{i,j}=\left\{s^i\left(x_j\right)s^j\left(y_j\right)|x\in X.y\in Y,xy\in F\right\}$。

易证每一个图 $F_{i,j}\left(1\le i\le r_1,1\le i\le r_2\right)$ 都是γK_m,n的K_2,4-因子。于它们边集的并构成γK_m,n，因此 $\left\{F_{i,j}|1\le i\le r_1,1\le i\le r_2\right\}$ 就是γK_m,n的一个K_2,4-因子分解。

引理得证。

以下引理的证明同引理2.5相类似，因此我们只写出其中X，Y，E_i和 $E_p{}_{+i}$ 的表达式。

引理2.6：对于任意正整数γ，p和q，如果 $m=4\left(p+2q\right)\left(p+q\right)/\gamma$， $n=4\left(2p+q\right)\left(p+q\right)/\gamma$，则当 $\left(2p+q\right)/\gamma$ 是正整数时，γK_m,n存在K_2,4-因子分解。

证明：记 $a=2p\left(p+q\right)/\gamma$， $b=2q\left(p+q\right)/\gamma$， $r=\left(p+2q\right)\left(2p+q\right)$， $r_1=p+2q$ 和 $r_2=2p+q$。并令

$X=\left\{x_{i,j}|\text{1}\le i\le r_{\text{1}}\text{,1}\le j\le \text{4}\left(p+q\right)/\gamma \right\}$，

$Y=\left\{y_{i,j}|1\le i\le r_2,1\le j\le 4\left(p+q\right)/\gamma \right\}$。

对于每一个正整数i，x，y，z，1 £ i £ p，0 £ x，y，z £ 1，令 $f\left(x\right)=\text{2}\left(p+q\right)x/\gamma$， $g\left(i,y\right)=2\left(i-1\right)+y+1$， $h\left(i,y,z\right)=4\left(i-1\right)+y+4\left(p+q\right)z/\gamma$ 并构作如下边集

$E_i=\left\{x_i{}_{,f\left(x\right)+j}{y}_g{}_{\left(i,y\right),h\left(i,y,z\right)+j}:1\le j\le 2\left(p+q\right)/\gamma ,0\le x,y,z\le 1\right\}$。

对于每一个正整数i，x，y，z，1 £ i £ q，0 £ x，y，z £ 1，令 $f\left(x\right)=\text{2}\left(p+q\right)x/\gamma$， $g\left(i,y\right)=2\left(i-1\right)+y+1$， $u\left(i,y,z\right)=2p+2\left(p+q\right)z/\gamma +2\left(i-1\right)+y+1$ 并构作如下边集

$E_p{}_{+i}=\left\{x_p{}_{+g\left(i,y\right),f\left(x\right)+j}{y}_{2p+i,u\left(i,y,z\right)+j}:1\le j\le 2\left(p+q\right)/\gamma ,0\le x,y,z\le 1\right\}$。

引理2.7：对于任意正整数γ，p和q，如果 $m=2\left(p+8q\right)\left(p+4q\right)/\gamma$， $n=4\left(p+2q\right)\left(p+4q\right)/\gamma$。则当 $\left(p+4q\right)/\gamma$ 是正整数时，γK_m,n存在K_2,4-因子分解。

证明：记 $a=p\left(p+4q\right)/\gamma$， $b=4q\left(p+4q\right)/\gamma$， $r=\left(p+8q\right)\left(p+2q\right)$， $r_1=p+8q$ 和 $r_2=p+2q$。并令

$X=\left\{x_{i,j}|\text{1}\le i\le r_{\text{1}}\text{,1}\le j\le \text{2}\left(p+4q\right)/\gamma \right\}$，

$Y=\left\{y_{i,j}|\text{1}\le i\le r_2\text{,1}\le j\le 4\left(p+4q\right)/\gamma \right\}$。

对于每一个正整数i，x，y，1 £ i £ p，0 £ x £ 1和0 £ y £ 3，令 $f\left(x\right)=\left(p+4q\right)x/\gamma$， $g\left(i,y\right)=i-1+\left(p+4q\right)y$，并构作如下边集

$E_i=\left\{x_i{}_{,f\left(x\right)+j}{y}_i{}_{,g\left(i,y\right)+j}:1\le j\le \left(p+4q\right)/\gamma ,0\le x\le 1,0\le y\le 3\right\}$。

对于每一个正整数i，x，y，z，w，1 £ i £ q，0 £ y，w £ 1和0 £ x，z £ 3，令 $h\left(i,x,y\right)=p+8\left(i-1\right)+2x+y$， $u\left(i,x,w\right)=p+4\left(i-1\right)+x+\left(p+4q\right)w/\gamma$ 并构作如下边集

$E_p{}_{+i}=\{x_h{}_{\left(i,x,y\right),\left(p+4q\right)z/\gamma +j}{y}_p{}_{+2\left(i-1\right)+y,u\left(i,x,w\right)+j}:1\le j\le \left(p+4q\right)/\gamma ,0\le y,w\le 1和0\le x,z\le 3\}$。

引理2.8：对于任意正整数γ，p和q，如果 $m=2\left(p+16q\right)\left(p+8q\right)/\gamma$， $n=4\left(p+4q\right)\left(p+8q\right)/\gamma$。则当 $\left(p+8q\right)/\gamma$ 是正整数时，γK_m,n存在K_2,4-因子分解。

证明：记 $a=p\left(p+8q\right)/\gamma$， $b=8q\left(p+8q\right)/\gamma$， $r=\left(p+16q\right)\left(p+4q\right)$， $$ 和 $r_2=p+4q$。并令

$X=\left\{x_{i,j}|\text{1}\le i\le r_{\text{1}}\text{,1}\le j\le \text{2}\left(p+8q\right)/\gamma \right\}$，

$Y=\left\{y_{i,j}|\text{1}\le i\le r_{\text{2}}\text{,1}\le j\le \text{4}\left(p+8q\right)/\gamma \right\}$。

对于每一个正整数i，x，y，满足1 £ i £ p，0 £ x £ 1和0 £ y £ 3，令 $f\left(x\right)=\left(p+8q\right)x/\gamma$， $g\left(i,y\right)=\left(p+8q\right)y/\gamma +i-1$，并构作如下边集

$E_i=\left\{x_i{}_{,f\left(x\right)+j}{y}_i{}_{,g\left(i,y\right)+1}:\text{1}\le j\le \left(p+\text{8}q\right)/\gamma ,0\le x\le \text{1,}0\le y\le \text{3}\right\}$。

对于每一个正整数i，x，y，z，s，t，且1 £ i £ q，0 £ x £ 3，0 £ y，z，s，t £ 1，令 $h\left(i,x,y,z\right)=p+16\left(i-1\right)+4x+2y+z+1$， $u\left(s\right)=\left(p+8q\right)s/\gamma ,v\left(i,x\right)=p+4\left(i-1\right)+x+1$， $w\left(i,x,y,t\right)=p+8\left(i-1\right)+2x+y+1+\left(p+8q\right)y/\gamma +\left(p+8q\right)t/\gamma$ 并构作如下边集

$E_p{}_{+i}=\left\{x_h{}_{\left(i,x,y,z\right),u\left(s\right)+j}{y}_v{}_{\left(i,x\right),w\left(i,x,y,t\right)+j}:\text{1}\le j\le \left(p+\text{8}q\right)/\gamma ,0\le x\le \text{3},0\le y,z,s,t\le \text{1}\right\}$。

定理1.1的证明：定理1.1必要性的证明显然。结合引理2.2和引理2.8，即可完成定理1.1充分性的证明。

基金项目

国家自然科学基金资助项目(11571251)。