Advances in Applied Mathematics
Vol.
10
No.
08
(
2021
), Article ID:
44864
,
7
pages
10.12677/AAM.2021.108301
对称的完全二部多重有向图的
-因子分解
朱莉
南通职业大学,江苏 南通
收稿日期:2021年7月26日;录用日期:2021年8月23日;发布日期:2021年8月30日
摘要
如果对称完全二部多重有向图
的有向弧集可以分拆为
的
-因子,则称
存在
-因子分解。对称完全二部多重有向图
存在
-因子分解的充分必要条件是:1)
,2)
,3)
,4)
是整数。
关键词
二部多重有向图,因子,因子分解
-Factorization of Symmetric Complete Bipartite Multi-Digraphs
Li Zhu
Nantong Vocational University, Nantong Jiangsu
Received: Jul. 26th, 2021; accepted: Aug. 23rd, 2021; published: Aug. 30th, 2021
ABSTRACT
A
-factorization
is a set of arc-disjoint
-factors of
. A necessary and sufficient condition for
-factorization of
is that: 1)
, 2)
, 3)
and 4)
.
Keywords:Complete Bipartite Multi-Digraphs, Factor, Factorization
Copyright © 2021 by author(s) and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
1. 引言
本文所涉及的图均为有向图。
表示对称完全二部有向图,其点集划分为X和Y两个部分,分别具有m和n个点。
中来自不同部分的两个点有两条方向相反的有向弧相连,同一部分的两个点无有向弧相连。
表示多重图,它是
个
的并。如果
的子图F包含了图的所有点,则称F为
的一个生成子图。
是具有k个点的有向路。若
生成子图F的每个分支均同构于图
,则称F为
的一个
-因子。如果
有向弧集可以分拆为
的
-因子,则称
存在
-因子分解。在文献 [1] 中,Ushio称
的
-因子分解为可分解的
二部有向路设计。如果
存在
-因子分解,则称
是可
-因子分解的。本文涉及到的其他图论概念,均参照图论著作 [2] [3]。
的
-因子分解存在性问题已有许多研究结论。k是偶数时,Ushio [1]、Wang [4] 和Du [5] 完全解决了
的
-因子分解的存在性问题。k是奇数时,
的
-因子分解的存在性问题复杂了很多。当
时,Ushio [6]、Du [7] 和Wang [8],完全解决了
的
-因子分解的存在性问题。当
时,Wang和Du [9],完全解决了
的
-因子分解的存在性问题。本文研究当
时,对称完全二部多重有向图
的
-因子分解的存在性。即证明
存在
-因子分解的充分必要条件。
定理1.1 对称完全二部多重有向图
存在
-因子分解的充分必要条件是:1)
,2)
,3)
,4)
是整数。
2. 主要结论
通过简单计算,可得
存在
-因子分解的必要条件。
定理2.1 如果对称完全二部多重有向图
存在
-因子分解,则1)
,2)
,3)
,4)
是整数。
为了证明
存在
-因子分解的充分条件,需要以下几个引理,其中
表示a和b的最大公约数。
引理2.2 设
和v是正整数。如果
,则
。
引理2.3 设s是任意正整数。如果
存在
-因子分解,则
存在
-因子分解。
引理2.4 设s是任意正整数。如果
存在
-因子分解,则
存在
-因子分解。
引理2.2~2.4的证明参见文献 [7] [8]。
引理2.5
存在
-因子分解。
证明设
的两个部分点集为
和
,则
,,,
是
的
-因子分解。
根据引理2.3、2.4和2.5,可得以下结论。
引理2.6 当
或
时,
存在
-因子分解。
考虑
且
时的情形。此时,设
,, 和
。显然
是整数,同时
,。于是
,。可得
。令
,则z是整数。令
,,,。因而
。通过计算可得下列各式:
为了对上面的则有式子进行分类,我们引入以下引理
引理2.7 1) 假设
,,令
,那么
,,
,,
这里s为正整数。
2) 假设
,,设
,令
,那么
,,
,,
这里s为正整数。
3) 假设
,,设
,令
,那么
,,
,,
这里s为正整数。
4) 假设
,,设
,令
,那么
,,
,,
这里s为正整数。
5) 假设
,,设
,令
,那么
,,
,,
这里s为正整数。
6) 假设
,,设
,令
,那么
,,
,,
这里s为正整数。
7) 假设
,,设
,,令
,那么
,,
,,
这里s为正整数。
8) 假设
,,设
,,令
,那么
,,
,,
这里s为正整数。
9) 假设
,,设
,,令
,那么
,,
,,
这里s为正整数。
10) 假设
,,设
,,令
,那么
,,
,,
这里s为正整数。
11) 假设
,,设
,令
,那么
,,
,,
这里s为正整数。
12) 假设
,,设
,,令
,那么
,,
,,
这里s为正整数。
13) 假设
,,设
,,令
,那么
,,
,,
这里s为正整数。
14) 假设
,,设
,,令
,那么
,,
,,
这里s为正整数。
15) 假设
,,设
,,令
,那么
,,
,,
这里s为正整数。
证明 (1)根据题意有
,所以
且
。这样
。
根据引理2.2,得
。于是
是正整数。设
。令
,。由
,。可得
和
是正整数。由于
,因此
是正整数,其中
。记
,于是可得1)中的结论。
2)~15)中各式的结论同理可证。
引理2.8 设
,p和q是正整数,如果
,,那么当
是正整数时,
存在
-因子分解。
证明 设
,,, 和
。并设X和Y是多重二部图
的两个部分点集
,
。
以下通过直接构造,证明
存在
-因子分解。约定
的第一个下标i和第二个下标j分别在
和
中进行模
和模
的运算;
的第一个下标i和第二个下标j分别在
和
中进行模
和模
的运算。
对于正整数i,
,构造如下有向弧集
。
对于正整数i,
,构造如下有向弧集
。
记
,那么F是
的一个
-因子。定义一个双射
。
对于每一个i和每一个j(其中
, ),令
。
通过验证可知每一个
都是
的
-因子。并且它们有限弧集的并构成
,于是
就是
的一个
-因子分解。
下列引理2.9和引理2.10的证明过程同引理2.8类似,我们在证明中只写出二部图的两个部分点集X、Y的表达式和有向弧集
、
的表达式。
引理2.9 设
,p和q是正整数,如果
,,那么当
是正整数时,
存在
-因子分解。
证明 设
,,, 和
。并设
,
。
对于正整数i (
),构造有向弧集
对于正整数i (
),构造有向弧集
。
引理2.10 设
,p和q是正整数,如果
,,那么当
是正整数时,
存在
-因子分解。
证明 设
,,, 和
。并设
,
。
对于正整数i (
),构造有向弧集
。
对于正整数i (
),构造有向弧集
。
引理2.8~2.10构造了引理2.7中情形3、情形6和情形7的
-因子分解。分别令引理2.8中p的为
、
、
、
、
,可得到引理2.7中的情形2、情形8、情形1、情形4和情形5,再将情形1~7中的p和q互换,则得情形9~15。于是结合引理2.3~2.10,我们可得
存在
-因子分解的充分条件。
定理2.11 如果正整数
,m和n满足1)
,2)
,3)
,4)
是整数,则对称的完全二部多重有向图
存在
-因子分解。
结合定理2.1和定理2.11,即可完成定理1.1的证明。
基金项目
国家自然科学基金资助项目(11571251)。
文章引用
朱 莉. 对称的完全二部多重有向图的P7⇀-因子分解
P7⇀-Factorization of Symmetric Complete Bipartite Multi-Digraphs[J]. 应用数学进展, 2021, 10(08): 2881-2887. https://doi.org/10.12677/AAM.2021.108301
参考文献
- 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.