DOI:10.12677/AAM.2021.108301,PDF,HTML,XML,被引量下载: 411浏览: 551国家自然科学基金支持
作者:朱 莉：南通职业大学，江苏 南通
关键词:二部多重有向图；因子；因子分解；Complete Bipartite Multi-Digraphs；Factor；Factorization

文章引用：朱莉. 对称的完全二部多重有向图的 _P7 ^⇀-因子分解[J]. 应用数学进展, 2021, 10(8): 2881-2887. https://doi.org/10.12677/AAM.2021.108301

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)。

参考文献

[1]	Ushio, K. (1993) G-Designs and Related Designs. Discrete Mathematics, 116, 299-311. https://doi.org/10.1016/0012-365X(93)90408-L
[2]	Harary, F. (1972) Graph Theory. Addison-Wesley, Massachusetts.
[3]	Chartrand, G. and Lesniak, L. (1986) Graphs and Digraphs. 2nd Edition, Wadsworth, California.
[4]	Wang, H. (1993) P2k-Factorization of Complete Bipartite Graph. Discrete Mathematics, 120, 307-308. https://doi.org/10.1016/0012-365X(93)90593-I
[5]	Du, B.L. (2000) P2k-Factorization of Complete Bipartite Multigraphs. The Australasian Journal of Combinatorics, 21, 275-278.
[6]	Ushio, K. (1988) P3-Factorization of Complete Bipartite Graphs. Discrete Mathematics, 72, 361-366. https://doi.org/10.1016/S0167-5060(08)70804-5
[7]	Du, B.L. (2003) -Factorization of Complete Bipartite Symmetric Digraphs. The Australasian Journal of Combinatorics, 19, 275-278.
[8]	Wang, J. and Du, B.L. (2003) -Factorization of Complete Bipartite Multigraphs and Symmetric Complete Bipartite Multi-Digraphs. Utilitas Mathematic, 63, 213-228.
[9]	Wang, J. and Du, B.L. (2005) -Factorization of Symmetric Complete Bipartite Multi-Digraphs. Utilitas Mathematic, 79, 129-137.