1. 引言
对于某个整数t ≥ 4,如果G和H是
的两个边不交的、非同构的、无孤立点的生成子图且满足
,那么称
是阶为t的图对。如果
是图G的边不交的子图且
,则我们说G有
-分解,并且记为
或
。对于
,如果
,那么我们说G有H-分解。对于
,给定一个阶为t的图对
,如果
或
且
中至少存在一个S的复制和T的复制,那么我们说G存在阶为t的图对分解且记为G有
-分解。设
表示n个顶点的圈,记为
。我们把两条点不交的边记为
。显然在上述定义下,阶为4的图对是
。注意到,如果G存在
-分解,那么
存在
-分解。
设G是一个简单图,将G的每条边变成
条边得到的重图记为
。简单图G和H的笛卡尔积记为
,其中
,
或
。显然,
。设
表示n个顶点的完全图,其中
。设
表示完全二部图
,其中
,
。尚未给出的图论术语见文献 [1] [2] 。
图分解的存在性问题一直受到众多学者的广泛关注 [3] - [8] 。其中针对阶为t的图对分解的问题,国内外许多学者对其进行了研究与探索并取得了许多结果。2003年,Abueida和Daven [9] 给出了完全图
的阶为4和5的图对分解的充要条件。作为其结论的推广:2004年,刘萍 [10] 得到了完全多部图
的阶为4和5的图对分解的充要条件。2005年,Abueida [11] 等人研究
的阶为4和5的图对分解的存在性,给出了
的阶为4和5的图对分解的充要条件。2015年,Gao和Roberts [12] 给出了完全图
的阶为6的图对分解的充要条件。2013年,Abueida和Daven [13] 考虑特殊图的笛卡尔积的阶为4的图对分解的存在性,得到了
,
,
,
,
,
存在
-分解的充要条件。
受以上文献的启发,本文将给出
,
,
,
,
,
,
存在
-分解的充要条件。因为
,
,所以G存在
-分解的一个必要条件是
,
且
是偶数。显然,如果图G存在
-分解,那么图G存在
-分解。反过来,如果图G存在
-分解,那么图G不一定存在
-分解。例如:
存在
-分解,但
不存在
-分解。
2. 预备知识
本节给出了本文需要的一些基本概念和符号。
令图
,其中
是图G的顶点集,
是图G的边集。如果G是一个多重图,那么两个相同端点之间的边视为不同的边。任意非空子集
,
表示G的由S导出的子图。G的线图记为
。
定理2.1
,
分别表示
和
,其中
,
。
定理2.2
表示
,其中
。
定理2.3 [13]
存在
-分解当且仅1)
都是偶数且当
时,
,2)
都是偶数且当
时,
,或3)
都是奇数且
,
。
定理2.4 [13]
存在
-分解当且仅当
,
且为整数。
定理2.5 [13]
存在
-分解当且仅当1)
都是偶数且当
时,
,2)
都是偶数且当
时,
,或3) m为奇数,
且
。
定理2.6 [13]
存在
-分解当且仅当1) m是偶数,
,或2) m是奇数且
。
定理2.7 [13]
存在
-分解当且仅当满足下列条件之一:1)
且当
时,
,2) m或n) 是奇数且
,3)
且当
时,
,或4)
。
定理2.8 [11] 如果
,下列结论是正确的:
1)
存在
-分解当且仅当
且
。
2) 如果
且
是偶数,那么
存在
-分解。
定理2.9 [14] 设
是整数,
且
。
存在
-分解当且仅当1)
,2)
是偶数且3)
。
定理2.10 [15]
存在
-分解当且仅当1) n是偶数,2)
,
,3)
,
,或4)
,
是奇数。
3. 主要结论及其证明
定理3.1
存在
-分解当且仅当1)
,2)
且是偶数。
证明 假设
存在
-分解。因为
且
,所以
,
且偶数。因此,必要性得证。
下证充分性。设
。我们分以下两种情况讨论:
情形1
奇偶性相同。
当
同为奇数,由定理2.3,我们有
存在
-分解。
当
同为偶数且
或
,由定理2.3,我们有
存在
-分解。
当
,因为
,所以
。对于
,设
,
,
。那么,
。因此,
存在
-分解。
情形2
奇偶性不同。
因为
是偶数,所以
是偶数。
对于
,
,设
,
,
。那么,
。因此,
存在
-分解。
定理3.2
存在
-分解当且仅当1)
,2)
且是偶数。
证明 假设
存在
-分解。因为
且
,所以
,
且是偶数。因此,必要性得证。
下证充分性。设
。我们分以下两种情况讨论:
情形1 n是偶数。
由定理2.4,
存在
-分解。
情形2 n是奇数。
因为
是偶数,所以
是偶数。对于
,设
。那么,
。由定理3.1,
存在
-分解。
定理3.3
存在
-分解当且仅当1)
,2)
且是偶数,且3)
。
证明 假设
存在
-分解。因为
且
,所以
,
且是偶数。当
时,
。由于
不存在
,因此
不存在
-分解。因此,必要性得证。
下证充分性。设
。当
时,
,由定理3.1,我们有
存在
-分解。当
时,
,由定理3.2,我们有
存在
-分解。因此,设
。我们分以下四种情况讨论:
情形1
。
由定理2.5,我们有
存在
-分解。
情形2
。
当m为奇数,由定理2.5,我们有
存在
-分解。
当m为偶数。因为
是偶数,所以
是偶数。对于
,
,设
。
。显然,
。由定理2.8和2.9,我们有
存在
-分解。
情形3
。
当m为偶数,由定理2.5,我们有
存在
-分解。
当m为奇数。因为
是偶数,所以
是偶数。对于
,
,设
。
。显然,
。由定理2.8,我们有
存在
-分解。
情形4
。
因为
是偶数,所以
是偶数。对于
,
,设
。
。显然,
。由定理2.8,我们有
存在
-分解。
定理 3.4
存在
-分解当且仅当1)
,2)
且是偶数,且3) 当
时,
。
证明 假设
存在
-分解。因为
且
,所以
,
且是偶数。当
时,
。假设
,那么
不包含
。因此,必要性得证。
下证充分性。设
。当
,
,由定理3.2,我们有
存在
-分解。因此,设
。我们分以下两种情况讨论:
情形1 m是偶数。
当
,由定理2.6,我们有
存在
-分解。
当
。因为
,所以
。对于
,设
,
,
。那么,
。因此,
存在
-分解。
情形2 m是奇数。
当
。由定理2.6,我们有
存在
-分解。
当
。因为
是偶数,所以
是偶数。对于
,设
。那么,
。由定理3.3,
存在
-分解。
定理3.5
存在
-分解当且仅当1)
,2)
且是偶数,且3) 当
,
时,
。
证明 假设
存在
-分解。因为
且
,所以
,
且是偶数。当
,
时,
。由定理2.8,
不存在
-分解。所以,当
,
时,
。因此,必要性得证。
下证充分性。设
。当
时,
,由定理3.3,
存在
-分解。当
时,
,由定理3.4,
存在
-分解。当
时,
。当
时,由定理2.8,
存在
-分解。当
且
是偶数时,由定理2.9,我们有
存在
-分解。因为
,所以
存在
-分解。当
且
是奇数时,设
,
,
,
,
。那么,
。因此,
存在
-分解。因此,设
,
。我们分以下三种情况讨论:
情形1
是偶数。
由定理2.7,我们有
存在
-分解。
情形2
是奇数。
设
,
。不失一般性,我们假设
。因为
是奇数,所以
是偶数。因为
是偶数,所以
是偶数。因此,
满足:1)
,2)
,
是偶数。
当
,即
或
。由定理2.7,我们有
存在
-分解。
当
,即
,
。
注意到
,
,
。由定理2.8和2.9,我们有
存在
-分解。
情形3
是奇偶性不同。
不失一般性,假设m是偶数,n是奇数。
当
。由定理2.7,我们有
存在
-分解。
当
。因为
是偶数,所以
是偶数。注意到
,
,
。由定理2.8和2.9,我们有
存在
-分解。
定理3.6
存在
-分解当且仅当1)
,2)
且是偶数。
证明 假设
存在
-分解。因为
且
,所以
,
且是偶数。因此,必要性得证。
下证充分性。设
。我们分以下三种情况讨论:
情形1 n是偶数。
由定理2.10,
存在
-分解,因此
存在
-分解。
情形2
。
且
。由定理2.8,
存在
-分解。
情形3
。
因为
是偶数,所以
是偶数。
且
。由定理2.8,
存在
-分解。
4. 结语
本文给出了
,
,
,
,
,
存在
-分解的充要条件。在文献 [13] 中,
存在
-分解当且仅当
,
。因此,
存在
-分解的充要条件是
,
。注意到,
,因此本文也给出了
存在
-分解的充要条件。
本文仅仅考虑了上述多重图的阶为4的图对分解。在已有的基础上,我们还可以考虑上述图的阶为5或6的图对分解。