对称的完全二部多重有向图的_P7^⇀-因子分解

_P7^⇀-Factorization of Symmetric Complete Bipartite Multi-Digraphs

摘要: 如果对称完全二部多重有向图λK_m,n^*的有向弧集可以分拆为λK_m,n^*的_Pk^⇀-因子，则称λK_m,n^*存在_Pk^⇀-因子分解。对称完全二部多重有向图λK_m,n^*存在_P7^⇀-因子分解的充分必要条件是：1) 3m≤4n，2) 3n≤4m，3) m+n≡0(mod7)，4) 7λmn/[3(m,n)]是整数。

Abstract: A _Pk^⇀-factorization λK_m,n^* is a set of arc-disjoint _Pk^⇀-factors of λK_m,n^*. A necessary and sufficient condition for _P7^⇀-factorization of λK_m,n^* is that: 1) 3m≤4n, 2) 3n≤4m, 3) m+n≡0(mod7) and 4) 7λmn/[3(m,n)].

1. 引言

本文所涉及的图均为有向图。 $K_{m,n}^{*}$ 表示对称完全二部有向图，其点集划分为X和Y两个部分，分别具有m和n个点。 $K_{m,n}^{*}$ 中来自不同部分的两个点有两条方向相反的有向弧相连，同一部分的两个点无有向弧相连。 $\lambda K_{m,n}^{*}$ 表示多重图，它是 $\lambda$ 个 $K_{m,n}^{*}$ 的并。如果 $\lambda K_{m,n}^{*}$ 的子图F包含了图的所有点，则称F为 $\lambda K_{m,n}^{*}$ 的一个生成子图。 ${\stackrel{\rightharpoonup }{P}}_k$ 是具有k个点的有向路。若 $\lambda K_{m,n}^{*}$ 生成子图F的每个分支均同构于图 ${\stackrel{\rightharpoonup }{P}}_k$，则称F为 $\lambda K_{m,n}^{*}$ 的一个 ${\stackrel{\rightharpoonup }{P}}_k$ -因子。如果 $\lambda K_{m,n}^{*}$ 有向弧集可以分拆为 $\lambda K_{m,n}^{*}$ 的 ${\stackrel{\rightharpoonup }{P}}_k$ -因子，则称 $\lambda K_{m,n}^{*}$ 存在 ${\stackrel{\rightharpoonup }{P}}_k$ -因子分解。在文献 [1] 中，Ushio称 $\lambda K_{m,n}^{*}$ 的 ${\stackrel{\rightharpoonup }{P}}_k$ -因子分解为可分解的 $\left(m,n,k,\lambda \right)$ 二部有向路设计。如果 $\lambda K_{m,n}^{*}$ 存在 ${\stackrel{\rightharpoonup }{P}}_k$ -因子分解，则称 $\lambda K_{m,n}^{*}$ 是可 ${\stackrel{\rightharpoonup }{P}}_k$ -因子分解的。本文涉及到的其他图论概念，均参照图论著作 [2] [3]。

$\lambda K_{m,n}^{*}$ 的 ${\stackrel{\rightharpoonup }{P}}_k$ -因子分解存在性问题已有许多研究结论。k是偶数时，Ushio [1]、Wang [4] 和Du [5] 完全解决了 $\lambda K_{m,n}^{*}$ 的 ${\stackrel{\rightharpoonup }{P}}_k$ -因子分解的存在性问题。k是奇数时， $\lambda K_{m,n}^{*}$ 的 ${\stackrel{\rightharpoonup }{P}}_k$ -因子分解的存在性问题复杂了很多。当 $k=3$ 时，Ushio [6]、Du [7] 和Wang [8]，完全解决了 $\lambda K_{m,n}^{*}$ 的 ${\stackrel{\rightharpoonup }{P}}_3$ -因子分解的存在性问题。当 $k=5$ 时，Wang和Du [9]，完全解决了 $\lambda K_{m,n}^{*}$ 的 ${\stackrel{\rightharpoonup }{P}}_5$ -因子分解的存在性问题。本文研究当 $k=7$ 时，对称完全二部多重有向图 $\lambda K_{m,n}^{*}$ 的 ${\stackrel{\rightharpoonup }{P}}_7$ -因子分解的存在性。即证明 $\lambda K_{m,n}^{*}$ 存在 ${\stackrel{\rightharpoonup }{P}}_7$ -因子分解的充分必要条件。

定理1.1 对称完全二部多重有向图 $\lambda K_{m,n}^{*}$ 存在 ${\stackrel{\rightharpoonup }{P}}_7$ -因子分解的充分必要条件是：1) $3m\le 4n$，2) $3n\le 4m$，3) $m+n\equiv 0\left(\mathrm{mod}7\right)$，4) $7\lambda mn/\left[3\left(m+n\right)\right]$ 是整数。

2. 主要结论

通过简单计算，可得 $\lambda K_{m,n}^{*}$ 存在 ${\stackrel{\rightharpoonup }{P}}_7$ -因子分解的必要条件。

定理2.1 如果对称完全二部多重有向图 $\lambda K_{m,n}^{*}$ 存在 ${\stackrel{\rightharpoonup }{P}}_7$ -因子分解，则1) $3m\le 4n$，2) $3n\le 4m$，3) $m+n\equiv 0\left(\mathrm{mod}7\right)$，4) $7\lambda mn/\left[3\left(m+n\right)\right]$ 是整数。

为了证明 $\lambda K_{m,n}^{*}$ 存在 ${\stackrel{\rightharpoonup }{P}}_7$ -因子分解的充分条件，需要以下几个引理，其中 $\gcd \left(a,b\right)$ 表示a和b的最大公约数。

引理2.2 设 $a,b,u$ 和v是正整数。如果 $\gcd \left(au,bv\right)=1$，则 $\gcd \left(uv,au+bv\right)=1$。

引理2.3 设s是任意正整数。如果 $\lambda K_{m,n}^{*}$ 存在 ${\stackrel{\rightharpoonup }{P}}_7$ -因子分解，则 $\lambda s{K}_{m,n}^{*}$ 存在 ${\stackrel{\rightharpoonup }{P}}_7$ -因子分解。

引理2.4 设s是任意正整数。如果 $\lambda K_{m,n}^{*}$ 存在 ${\stackrel{\rightharpoonup }{P}}_7$ -因子分解，则 $\lambda K_{ms,ns}^{*}$ 存在 ${\stackrel{\rightharpoonup }{P}}_7$ -因子分解。

引理2.2~2.4的证明参见文献 [7] [8]。

引理2.5 $K_{3,4}^{*}$ 存在 ${\stackrel{\rightharpoonup }{P}}_7$ -因子分解。

证明设 $K_{3,4}^{*}$ 的两个部分点集为 $\left\{x_1,x_2,x_3\right\}$ 和 $\left\{y_1,y_2,y_3,y_4\right\}$，则

$y_1{x}_1{y}_2{x}_2{y}_3{x}_3{y}_4$， $y_4{x}_3{y}_3{x}_2{y}_2{x}_1{y}_1$， $y_3{x}_1{y}_4{x}_2{y}_1{x}_3{y}_2$， $y_2{x}_3{y}_1{x}_2{y}_4{x}_1{y}_3$

是 $K_{3,4}^{*}$ 的 ${\stackrel{\rightharpoonup }{P}}_7$ -因子分解。

根据引理2.3、2.4和2.5，可得以下结论。

引理2.6 当 $4m=3n$ 或 $4n=3m$ 时， $\lambda K_{m,n}^{*}$ 存在 ${\stackrel{\rightharpoonup }{P}}_7$ -因子分解。

考虑 $3m<4n$ 且 $3n<4m$ 时的情形。此时，设 $a=\left(4n-3m\right)/7$， $b=\left(4m-3n\right)/7$， $t=\left(m+n\right)/7$ 和 $r=7\lambda mn/\left[3\left(m+n\right)\right]$。显然 $a,b,t,r$ 是整数，同时 $0<a<m$， $0<b<n$。于是 $3a+4b=m$， $4a+3b=n$。可得 $r=4\lambda \left(a+b\right)+\lambda ab/\left[3\left(a+b\right)\right]$。令 $z=\lambda ab/\left[3\left(a+b\right)\right]$，则z是整数。令 $\gcd \left(3a,4b\right)=d$， $3a=dp$， $4b=dq$， $\gcd \left(p,q\right)=1$。因而 $z=\lambda dpq/\left[3\left(4p+3q\right)\right]$。通过计算可得下列各式：

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

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

$n=\left(16p+9q\right)\left(4p+3q\right)z/\left(4\lambda pq\right)$

$r=\left(p+q\right)\left(16p+9q\right)z/(\; p\; q\; )$

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

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

为了对上面的则有式子进行分类，我们引入以下引理

引理2.7 1) 假设 $\gcd \left(p,9\right)=1$， $\gcd \left(q,16\right)=1$，令 $\gcd \left(4p+3q,\lambda \right)=\gamma$，那么

$m=12\left(p+q\right)\left(4p+3q\right)s/\gamma$， $n=\left(16p+9q\right)\left(4p+3q\right)s/\gamma$，

$r=4\left(p+q\right)\left(16p+9q\right)s\lambda /\gamma$， $a=4p\left(4p+3q\right)s/\gamma$， $b=3q\left(4p+3q\right)s/\gamma$

这里s为正整数。

2) 假设 $\gcd \left(p,9\right)=1$， $\gcd \left(q,16\right)=2$，设 $q=2q_1$，令 $\gcd \left(2p+3q_1,\lambda \right)=\gamma$，那么

$m=6\left(p+2q_1\right)\left(2p+3q_1\right)s/\gamma$， $n=\left(8p+9q_1\right)\left(2p+3q_1\right)s/\gamma$，

$r=2\left(p+2q_1\right)\left(8p+9q_1\right)s\lambda /\gamma$， $a=2p\left(2p+3q_1\right)s/\gamma$， $b=3q_1\left(2p+3q_1\right)s/\gamma$

这里s为正整数。

3) 假设 $\gcd \left(p,9\right)=1$， $\gcd \left(q,16\right)=4$，设 $q=4q_2$，令 $\gcd \left(2\left(p+3q_2\right),\lambda \right)=\gamma$，那么

$m=3\left(p+4q_2\right)\left(p+3q_2\right)s/\gamma$， $n=\left(4p+9q_2\right)\left(p+3q_2\right)s/\gamma$，

$r=\left(p+4q_2\right)\left(4p+9q_2\right)s\lambda /\gamma$， $a=p\left(p+3q_2\right)s/\gamma$， $b=3q_2\left(p+3q_2\right)s/\gamma$

这里s为正整数。

4) 假设 $\gcd \left(p,9\right)=1$， $\gcd \left(q,16\right)=8$，设 $q=8q_3$，令 $\gcd \left(p+6q_3,\lambda \right)=\gamma$，那么

$m=3\left(p+8q_3\right)\left(p+6q_3\right)s/\gamma$， $n=2\left(2p+9q_3\right)\left(p+6q_3\right)s/\gamma$，

$r=2\left(p+8q_3\right)\left(2p+9q_3\right)s\lambda /\gamma$， $a=p\left(p+6q_3\right)s/\gamma$， $b=6q_3\left(p+3q_3\right)s/\gamma$

这里s为正整数。

5) 假设 $\gcd \left(p,9\right)=1$， $\gcd \left(q,16\right)=16$，设 $q=16q_4$，令 $\gcd \left(p+12q_4,\lambda \right)=\gamma$，那么

$m=3\left(p+16q_4\right)\left(p+12q_4\right)s/\gamma$， $n=4\left(p+9q_4\right)\left(p+12q_4\right)s/\gamma$，

$r=4\left(p+16q_4\right)\left(p+9q_4\right)s\lambda /\gamma$， $a=p\left(p+12q_4\right)s/\gamma$， $b=12q_4\left(p+12q_4\right)s/\gamma$

这里s为正整数。

6) 假设 $\gcd \left(p,9\right)=3$， $\gcd \left(q,16\right)=1$，设 $p=3p_1$，令 $\gcd \left(3\left(4p_1+q\right),\lambda \right)=\gamma$，那么

$m=12\left(3p_1+q\right)\left(4p_1+q\right)s/\gamma$， $n=3\left(16p_1+3q\right)\left(4p_1+q\right)s/\gamma$，

$r=4\left(3p_1+q\right)\left(16p_1+3q\right)s\lambda /\gamma$， $a=12p_1\left(4p_1+q\right)s/\gamma$， $b=3q\left(4p_1+q\right)s/\gamma$

这里s为正整数。

7) 假设 $\gcd \left(p,9\right)=3$， $\gcd \left(q,16\right)=2$，设 $p=3p_1$， $q=2q_1$，令 $\gcd \left(2p_1+q_1,\lambda \right)=\gamma$，那么

$m=6\left(3p_1+2q_1\right)\left(2p_1+q_1\right)s/\gamma$， $n=3\left(8p_1+3q_1\right)\left(2p_1+q_1\right)s/\gamma$，

$r=2\left(3p_1+2q_1\right)\left(8p_1+3q_1\right)s\lambda /\gamma$， $a=6p_1\left(2p_1+q_1\right)s/\gamma$， $b=3q_1\left(2p_1+q\right)s/\gamma$

这里s为正整数。

8) 假设 $\gcd \left(p,9\right)=3$， $\gcd \left(q,16\right)=4$，设 $p=3p_1$， $q=4q_2$，令 $\gcd \left(6\left(p_1+q_2\right),\lambda \right)=\gamma$，那么

$m=3\left(3p_1+4q_2\right)\left(p_1+q_2\right)s/\gamma$， $n=3\left(4p_1+3q_2\right)\left(p_1+q_2\right)s/\gamma$，

$r=2\left(3p_1+4q_2\right)\left(4p_1+3q_2\right)s\lambda /\gamma$， $a=3p_1\left(p_1+q_2\right)s/\gamma$， $b=3q_2\left(p_1+q_2\right)s/\gamma$

这里s为正整数。

9) 假设 $\gcd \left(p,9\right)=3$， $\gcd \left(q,16\right)=8$，设 $p=3p_1$， $q=8q_3$，令 $\gcd \left(3\left(p_1+2q_3\right),\lambda \right)=\gamma$，那么

$m=3\left(3p_1+8q_3\right)\left(p_1+2q_3\right)s/\gamma$， $n=6\left(2p_1+3q_3\right)\left(p_1+2q_3\right)s/\gamma$，

$r=2\left(3p_1+8q_3\right)\left(2p_1+3q_3\right)s\lambda /\gamma$， $a=3p_1\left(p_1+2q_3\right)s/\gamma$， $b=6q\left(p_1+2q_3\right)s/\gamma$

这里s为正整数。

10) 假设 $\gcd \left(p,9\right)=3$， $\gcd \left(q,16\right)=16$，设 $p=3p_1$， $q=16q_4$，令 $\gcd \left(3\left(p_1+4q_4\right),\lambda \right)=\gamma$，那么

$m=3\left(3p_1+16q_4\right)\left(p_1+4q_4\right)s/\gamma$， $n=12\left(p_1+3q_4\right)\left(p_1+4q_4\right)s/\gamma$，

$r=4\left(3p_1+16q_4\right)\left(p_1+3q_4\right)s\lambda /\gamma$， $a=3p_1\left(p_1+4q_4\right)s/\gamma$， $b=12q_4\left(p_1+4q_4\right)s/\gamma$

这里s为正整数。

11) 假设 $\gcd \left(p,9\right)=9$， $\gcd \left(q,16\right)=1$，设 $p=9p_2$，令 $\gcd \left(12p_2+q,\lambda \right)=\gamma$，那么

$m=4\left(9p_2+q\right)\left(12p_2+q\right)s/\gamma$， $n=3\left(16p_2+3q\right)\left(12p_2+q\right)s/\gamma$，

$r=4\left(9p_2+q\right)\left(16p_1+q\right)s\lambda /\gamma$， $a=12p_2\left(12p_2+q\right)s/\gamma$， $b=q\left(12p_2+q\right)s/\gamma$

这里s为正整数。

12) 假设 $\gcd \left(p,9\right)=9$， $\gcd \left(q,16\right)=2$，设 $p=9p_2$， $q=2q_1$，令 $\gcd \left(6p_2+q_1,\lambda \right)=\gamma$，那么

$m=2\left(9p_2+2q_1\right)\left(6p_2+q_1\right)s/\gamma$， $n=3\left(8p_2+q_1\right)\left(6p_2+q_1\right)s/\gamma$，

$r=2\left(9p_2+2q_1\right)\left(8p_2+3q_1\right)s\lambda /\gamma$， $a=6p_2\left(6p_2+q_1\right)s/\gamma$， $b=q_1\left(6p_2+q_1\right)s/\gamma$

这里s为正整数。

13) 假设 $\gcd \left(p,9\right)=9$， $\gcd \left(q,16\right)=4$，设 $p=9p_2$， $q=4q_2$，令 $\gcd \left(2\left(3p_2+q_2\right),\lambda \right)=\gamma$，那么

$m=\left(9p_2+4q_2\right)\left(3p_2+q_2\right)s/\gamma$， $n=3\left(4p_2+q_2\right)\left(3p_2+q_2\right)s/\gamma$，

$r=\left(9p_2+4q_2\right)\left(4p_2+q_2\right)s\lambda /\gamma$， $a=3p_2\left(3p_2+q_2\right)s/\gamma$， $b=q_2\left(3p_2+q_2\right)s/\gamma$

这里s为正整数。

14) 假设 $\gcd \left(p,9\right)=9$， $\gcd \left(q,16\right)=8$，设 $p=9p_2$， $q=8q_3$，令 $\gcd \left(3p_2+2q_3,\lambda \right)=\gamma$，那么

$m=\left(9p_2+8q_3\right)\left(3p_2+2q_3\right)s/\gamma$， $n=6\left(2p_2+q_3\right)\left(3p_2+2q_3\right)s/\gamma$，

$r=2\left(9p_2+8q_3\right)\left(2p_2+q_3\right)s\lambda /\gamma$， $a=3p_2\left(3p_2+2q_3\right)s/\gamma$， $b=2q_3\left(3p_2+2q_3\right)s/\gamma$

这里s为正整数。

15) 假设 $\gcd \left(p,9\right)=9$， $\gcd \left(q,16\right)=16$，设 $p=9p_2$， $q=16q_4$，令 $\gcd \left(3p_2+4q_4,\lambda \right)=\gamma$，那么

$m=\left(9p_2+16q_4\right)\left(3p_2+4q_4\right)s/\gamma$， $n=12\left(p_2+q_4\right)\left(3p_2+4q_4\right)s/\gamma$，

$r=4\left(9p_2+16q_4\right)\left(p_2+q_4\right)s\lambda /\gamma$， $a=3p_2\left(3p_2+4q_4\right)s/\gamma$， $b=4q_4\left(3p_2+4q_4\right)s/\gamma$

这里s为正整数。

证明 (1)根据题意有 $\gcd \left(p,9\right)=\gcd \left(q,16\right)=\gcd \left(p,q\right)=1$，所以 $\gcd \left(16p+9q,2\right)=\gcd \left(4p+3q,2\right)=1$ 且 $\gcd \left(16p,9q\right)=\gcd \left(4p,3q\right)=1$。这样

$n=\left(16p+9q\right)\left(4p+3q\right)z/\left(4\lambda pq\right)$。

根据引理2.2，得 $\gcd \left(pq,16p+9q\right)=\gcd \left(pq,4p+3q\right)=1$。于是 $z/\left(4pq\right)$ 是正整数。设 $z^{\prime }=z/\left(4pq\right)$。令 $\gcd \left(4p\left(4p+3q\right),\lambda \right)={\gamma }_1$， $\gcd \left(q\left(4p+3q\right),\lambda \right)={\gamma }_2$。由 $a=4p\left(4p+3q\right)z^{\prime }/\lambda$， $b=3q\left(4p+3q\right)z^{\prime }/\lambda$。可得 $z^{\prime }{\gamma }_1/\lambda$ 和 $z^{\prime }{\gamma }_2/\lambda$ 是正整数。由于 $\gcd \left(4p,3q\right)=1$，因此 $z^{\prime }\gamma /\lambda$ 是正整数，其中 $\gcd \left(4p+3q,\lambda \right)=\gamma$。记 $s=z^{\prime }\gamma /\lambda$，于是可得1)中的结论。

2)~15)中各式的结论同理可证。

引理2.8 设 $\eta$，p和q是正整数，如果 $m=3\left(p+4q\right)\left(p+3q\right)$， $n=\left(4p+9q_2\right)\left(p+3q\right)$，那么当 $\left(p+3q\right)/\eta$ 是正整数时， $\eta K_{m,n}^{*}$ 存在 ${\stackrel{\rightharpoonup }{P}}_7$ -因子分解。

证明 设 $r=\left(p+4q\right)\left(4p+9q\right)$， $a=p\left(p+3q\right)$， $b=3q\left(p+3q\right)$， $r_1=p+4q$ 和 $r_2=4p+9q$。并设X和Y是多重二部图 $\eta K_{m,n}^{*}$ 的两个部分点集

$X=\left\{x_{ij}|1\le i\le r_1,1\le j\le 3\left(p+3q\right)/\eta \right\}$，

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

以下通过直接构造，证明 $\eta K_{m,n}$ 存在 ${\stackrel{\rightharpoonup }{P}}_7$ -因子分解。约定 $x_{ij}$ 的第一个下标i和第二个下标j分别在 $\left\{1,2,\cdots ,r_1\right\}$ 和 $\left\{1,2,\cdots ,3\left(p+3q\right)/\eta \right\}$ 中进行模 $r_1$ 和模 $3\left(p+3q\right)/\eta$ 的运算； $y_{ij}$ 的第一个下标i和第二个下标j分别在 $\left\{1,2,\cdots ,r_2\right\}$ 和 $\left\{1,2,\cdots ,\left(p+3q\right)/\eta \right\}$ 中进行模 $r_2$ 和模 $\left(p+3q\right)/\eta$ 的运算。

对于正整数i， $1\le i\le p$，构造如下有向弧集

$\begin{array}{l}{E}_i=\left\{x_{i,j+\left(u-1\right)\left(p+3q\right)/\eta }{y}_{4\left(i-1\right)+u,j+i}:1\le j\le \left(p+3q\right)/\eta ,1\le u\le 3\right\}\\ \cup \left\{y_{4\left(i-1\right)+u+1,j+i+1}{x}_{i,j+\left(u-1\right)\left(p+3q\right)/\eta }:1\le j\le \left(p+3q\right)/\eta ,1\le u\le 3\right\}\end{array}$。

对于正整数i， $1\le i\le q$，构造如下有向弧集

$\begin{array}{l}{E}_{p+i}=\left\{x_{p+4\left(i-1\right)+u,j+\left(v-1\right)\left(p+3q\right)/\eta }{y}_{4p+9\left(i-1\right)+3\left(v-1\right)+u,p+3\left(i-1\right)+u+j}:1\le j\le \left(p+3q\right)/\eta ,1\le u,v\le 3\right\}\\ \cup \left\{y_{4p+9\left(i-1\right)+3\left(v-1\right)+u,p+3\left(i-1\right)+u+j}{x}_{p+4\left(i-1\right)+u+1,j+\left(v-1\right)\left(p+3q\right)/\eta }:1\le j\le \left(p+3q\right)/\eta ,1\le u,v\le 3\right\}\end{array}$。

记 $F={\cup }_{1\le i\le p+q}{E}_i$，那么F是 $\eta K_{m,n}^{*}$ 的一个 ${\stackrel{\rightharpoonup }{P}}_7$ -因子。定义一个双射

$\sigma :\sigma \left(x_{i,j}\right)=x_{i+1,j},\sigma \left(y_{i,j}\right)=y_{i+1,j}$。

对于每一个i和每一个j(其中 $i\in \left\{1,2,\cdots ,r_1\right\}$， $j\in \left\{1,2,\cdots ,r_2\right\}$ )，令

$F_{i,j}=\left\{{\sigma }^i\left(x_j\right){\sigma }^i\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 j\le r_2\right)$ 都是 $\eta K_{m,n}^{*}$ 的 ${\stackrel{\rightharpoonup }{P}}_7$ -因子。并且它们有限弧集的并构成 $\eta K_{m,n}^{*}$，于是 $\left\{F_{i,j}\left(1\le i\le r_1,1\le j\le r_2\right)\right\}$ 就是 $\eta K_{m,n}^{*}$ 的一个 ${\stackrel{\rightharpoonup }{P}}_7$ -因子分解。

下列引理2.9和引理2.10的证明过程同引理2.8类似，我们在证明中只写出二部图的两个部分点集X、Y的表达式和有向弧集 $E_i$ 、 $E_{p+i}$ 的表达式。

引理2.9 设 $\eta$，p和q是正整数，如果 $m=12\left(3p+q\right)\left(4p+q\right)$， $n=3\left(16p+3q\right)\left(4p+q\right)$，那么当 $3\left(4p+q\right)/\eta$ 是正整数时， $\eta K_{m,n}^{*}$ 存在 ${\stackrel{\rightharpoonup }{P}}_7$ -因子分解。

证明 设 $r=4\left(3p+q\right)\left(16p+q\right)$， $a=12p\left(4p+q\right)$， $b=3q\left(4p+q\right)$， $r_1=4\left(3p+q\right)$ 和 $r_2=16p+q$。并设

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

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

对于正整数i ( $1\le i\le 4p$ )，构造有向弧集

$\begin{array}{l}{E}_i=\left\{x_{3\left(i-1\right)+u,j}{y}_{4\left(i-1\right)+u,j+3\left(i-1\right)+u}:1\le j\le 3\left(4p+q\right)/\eta ,1\le u\le 3\right\}\\ \cup \left\{y_{4\left(i-1\right)+u+1,j+3\left(i-1\right)+u+1}{x}_{3\left(i-1\right)+u,j}:1\le j\le 3\left(4p+q\right)/\eta ,1\le u\le 3\right\}\end{array}$

对于正整数i ( $1\le i\le q$ )，构造有向弧集

$\begin{array}{l}{E}_{p+i}=\left\{x_{12p+4\left(i-1\right)+u,j}{y}_{16p+3\left(i-1\right)+u,12p+3\left(i-1\right)+u+j}:1\le j\le 3\left(4p+q\right)/\eta ,1\le u\le 3\right\}\\ \cup \left\{y_{16p+3\left(i-1\right)+u,12p+3\left(i-1\right)+u+j}{x}_{12p+4\left(i-1\right)+u+1,j}:1\le j\le 3\left(4p+q\right)/\eta ,1\le u\le 3\right\}\end{array}$。

引理2.10 设 $\eta$，p和q是正整数，如果 $m=6\left(3p+2q\right)\left(2p+q\right)$， $n=3\left(8p+3q\right)\left(2p+q\right)$，那么当 $3\left(2p+q\right)/\eta$ 是正整数时， $\eta K_{m,n}^{*}$ 存在 ${\stackrel{\rightharpoonup }{P}}_7$ -因子分解。

证明 设 $r=2\left(3p+2q\right)\left(8p+3q\right)$， $a=6p\left(2p+q\right)$， $b=3q\left(2p+q\right)$， $r_1=2\left(3p+2q\right)$ 和 $r_2=8p+3q$。并设

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

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

对于正整数i ( $1\le i\le 2p$ )，构造有向弧集

$\begin{array}{l}{E}_i=\left\{x_{3\left(i-1\right)+u,j}{y}_{4\left(i-1\right)+u,j+3\left(i-1\right)+u}:1\le j\le 3\left(2p+q\right)/\eta ,1\le u\le 3\right\}\\ \cup \left\{y_{4\left(i-1\right)+u+1,j+3\left(i-1\right)+u+1}{x}_{3(i-1)+u,j}:1\le j\le 3\left(2p+q\right)/\eta ,1\le u\le 3\right\}\end{array}$。

对于正整数i ( $1\le i\le q$ )，构造有向弧集

$\begin{array}{l}{E}_{p+i}=\left\{x_{6p+4\left(i-1\right)+u,j}{y}_{8p+3\left(i-1\right)+u,6p+3\left(i-1\right)+u+j}:1\le j\le 3\left(2p+q\right)/\eta ,1\le u\le 3\right\}\\ \cup \left\{y_{8p+3\left(i-1\right)+u,6p+3\left(i-1\right)+u+j}{x}_{6p+4\left(i-1\right)+u+1,j}:1\le j\le 3\left(2p+q\right)/\eta ,1\le u\le 3\right\}\end{array}$。

引理2.8~2.10构造了引理2.7中情形3、情形6和情形7的 ${\stackrel{\rightharpoonup }{P}}_7$ -因子分解。分别令引理2.8中p的为 $2p^{\prime }$ 、 $3p^{\prime }$ 、 $4p^{\prime }$ 、 $2q^{\prime }$ 、 $4q^{\prime }$，可得到引理2.7中的情形2、情形8、情形1、情形4和情形5，再将情形1~7中的p和q互换，则得情形9~15。于是结合引理2.3~2.10，我们可得 $\lambda K_{m,n}^{*}$ 存在 ${\stackrel{\rightharpoonup }{P}}_7$ -因子分解的充分条件。

定理2.11 如果正整数 $\lambda$，m和n满足1) $3m\le 4n$，2) $3n\le 4m$，3) $m+n\equiv 0\left(\mathrm{mod}7\right)$，4) $7\lambda mn/\left[3\left(m+n\right)\right]$ 是整数，则对称的完全二部多重有向图 $\lambda K_{m,n}^{*}$ 存在 ${\stackrel{\rightharpoonup }{P}}_7$ -因子分解。

结合定理2.1和定理2.11，即可完成定理1.1的证明。

基金项目

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