ABSTRACT

Let G be a graph of order n with, where k is a positive integer. Suppose that, then the partition of G can be vertex disjoint 4-cliques and a chordal cycle, where the degree of vertexes in this chordal cycle is equal or greater than 3 or 4.

Keywords:Vertex-Disjoint, 4-Cliques, Chordal Cycle

图中具有指定性质的不交子图

王怡华¹，李硕²，衣晓宁¹

¹山东大学数学学院，山东 济南

²昌吉学院数学系，新疆 昌吉

收稿日期：2017年2月26日；录用日期：2017年3月18日；发布日期：2017年3月21日

摘 要

令G是一个顶点数为n的简单图，满足，k是任意正整数。假设，则图G可划分成个点不交的4-团和一个弦圈，使得弦圈上点的度大于等于3或4。

关键词 :点不交，4-团，弦圈

Copyright © 2017 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

本文中的图都为简单图。令是一个简单图，图G的顶点数和边数分别为和。图G中的一列子图称为独立的如果任意两个子图在G中没有公共点。若和在G中没有公共点，我们定义为和之间的边数。假设H是G的子图并且，表示u在H中的邻点，并且。对G中的子图U，令，且表示的导出子图。表示图G的最小度。同时，我们定义。我们用和分别表示顶点数为n的圈和路。路P称为图G的支撑路，如果路P覆盖图G中所有点。团是指G的一个完全子图，若一个团中包含的顶点数为k，则称其为k-团。

1963年，Erdös提出了一个关于图中包含k个点不交团的猜想。

猜想1 [1] 设G是一个顶点数为n的图。如果，s和k为正整数且。假设，那么G含有k个点不交的，即。

1970年，Hajnal和Szemeréd证明了该猜想，但他们的证明非常难懂，并且证明过程也非常复杂。1978年，Bollobós关于此猜想给出了简单的证明。当时，为如下定理。

定理1.1 [2] 设G是一个顶点数为n的图。如果，k为正整数。假设，那么G含有k个独立的4-团。

关于图中点不交的圈问题，1963年，Corrádi和Hajanal证明了下面定理。

定理1.2 [3] 设G是一个顶点数为n的图。如果，k为正整数。假设，那么G含有k个独立的圈。

最近Wang考虑了每个连通分支为固定大小的2-因子问题。

定理1.3 [4] 设G是一个顶点数为n的图。如果，k为正整数。假设，那么G有含有k个独立的圈的2-因子，其中k-1个为4-圈。

本文将定理1.3的4-圈推广到4-团，得到如下命题。

定理1.4 设G是一个顶点数为n的图。如果，k为正整数。假设，那么G含有k-1个独立的4-团和一个弦圈，弦圈上的度大于等于3或4。

在证明定理1.4之前，我们先引入下面几个引理。

2. 引理

引理2.1 设G是一个顶点数为n的图。如果，k为正整数。假设，那么G含有k个独立的4-团。

证明：

假设。令S为G中任意s个点的集合，则。因为最小度为整数且，所以。又因为，由定理1.1可知，图G含有k个点不交的4-团。□

引理2.2 令T为图G中的一个4-团并且令和为图G中不在T上的两个不相邻的点。如果，那么包含一个4-团和一条边e，使得和e是不交的并且e恰好与和中的一点相连。

证明：假设。因为，则设，所以点在T中的邻点中至少有三个，不妨设为。与边是不交的。□

引理2.3 [5] 如果为G中的一条路，，满足，那么G含有一个圈C 满足。另外，对于G中任意两个不相邻的点x,y，如果，那么G是哈密顿连通的。

令G是一个顶点数为n的图，定义G的(n+1)-闭包为从G中递归地连接每对度和至少为的不相邻的两个点所得到的图。

引理2.4 [6] 令G是一个顶点数为n的图，如果是完全图，那么G是哈密顿连通的。

引理2.5 [4] 假定且。那么对于任意，G含有一个4-圈Q满足有一条起始于x的哈密顿路。

3. 定理的证明

令G是一个顶点数为n的图，，k为正整数，满足条件。因为G有一个哈密顿圈，当时定理1.4成立。假设，令。为了证明，我们首先证明下列的断言。

断言3.1 G包含k个独立的4-团使得有一条哈密顿路P。并且当时，对任意。

证明：我们首先证明断言的情况。由引理2.1，时，断言是平凡的。如果，那么。由定理1.1，G包含个独立的4-团。所以当时，由引理2.1，G包含k个独立的4-团。令且。我们选择使得

(a) D中的路尽可能的长

当时，我们断言D包含一条边。否则，令为D中不相邻的两点。则，因此存在使得。由引理2.2，包含相互独立的一个4-团和一条边。这与选择(a)矛盾。这也证明断言对时成立。

假定。令为D中另外一点，且。所以。则存在，使得。 假设且。当时，不妨设。因为D中不含长度为3的路，所以点与不相邻。由引理2.2，则包含一个4-团并且，产生一条路，矛盾。因此。不妨设，类似地，包含一个4-团并且，产生一条路，矛盾。证明断言对时成立。

现在假定。首先我们证明下列命题成立。

(*)假定是G中l个独立的4-团且是的一条支撑路。则存在，使得包含一条支撑路。

如果不是，则。另外，我们可以假设包含一个哈密顿圈。否则，，则。由引理2.3，含有一个哈密顿圈。因为G是连通的，所以存在一个4-团使得。因此，包含一条支撑路。

令s为正整数，使得且。由引理2.1和当时的结论，我们可以找到个点不交的4-团，设为，和一条长度为的路。由递归可知，我们得到相互独立的k个4-团和一条顶点数为r的路P。

现在我们讨论时哈密顿路P上点的度。

由D中顶点数为r的哈密顿路P的构造过程可知，中与关联的点度大于等于4，与下一个4-团关联的点度大于等于4，其余两个点度大于等于3。

接下来讨论哈密顿路P中其余个点的度，。

当时，由定理1.1可知，G中包含个4-团，则这四个点可以组成一个4-团，设为，从中任选两点，不妨设为。则

因此在的个4-团中存在一个4-团，使得，则中至少存在两个不同的点与和相连，设两条关联的边为。因此包含一个哈密顿圈C，且在C中关联的四个点度大于等于4，非关联的点度大于等于3。 若，则在哈密顿路P上这四个点中有两个度大于等于4，两个大于等于3。若，则让替换中任意4-团，可以得到上述相同结果。

当时，设为。如果点与不相邻，则

所以在个4-团中存在一个4-团，使得，则。因此，点与在中的度大于等于3，点在中的度大于等于4。若，则在哈密顿路P上这三个点中有两个度大于等于3，一个大于等于4。否则，则让替换中任意4-团，可以得到上述相同结果。如果点与相邻，这三个点可以组成三角形，设为。则

所以在个4-团中存在一个4-团，使得。因此，与点与不相邻的情况类似，点，与在哈密顿路P上度大于等于4。

当时，这两个点组成路T，设。则

所以在个4-团中至少存在一个4-团，使得，则。因此，点在中的度大于等于4。若，则这两点在哈密顿路P上度大于等于4。否则，则让替换中任意4-团，可以得到上述相同结果。

当时，这个点设为x。则

所以在个4-团中至少存在一个4-团，使得。因此点x在中的度大于等于5。若，则这两点在哈密顿路P上度大于等于5。否则，则让替换中任意4-团，可以得到上述相同结果。

因此断言3.1成立。□

令，P为D中的一条哈密顿路，不妨设两个端点为。若，则存在，使得，设。由此可知与在中至少有一个共同点，设为，则。因此，是哈密顿的。即图G含有个4-团和一个哈密顿圈。由断言3.1可知，当时，这个哈密顿圈上点的度大于等于3或4。下面讨论当时哈密顿圈上的度。若，设这个点为x ，是平凡的，即所得哈密顿圈上点的度大于等于3或4。若，，则存在，使得，因此和在中至少有三个邻点，即哈密顿圈上点的度大于等于3或4。若，设路P上的三个点分别为，因为，所以存在，使得，则在中至少有三个邻点，即哈密顿圈上点的度大于等于3或4。若，由断言3.1可知，P为一个4-团，即哈密顿圈上点的度大于等于3或4。综上，当，主要定理得证。

否则，

(1)

则。由引理2.3，D含有一个圈C，使得。

断言3.2 如果，那么，对于任意且

证明：首先假定D中的每条哈密顿路的端点是邻接的。令P为D中的一条哈密顿路并且令。我们假定。假设，对于任意，存在一条哈密顿路。由假设可知，因为的极大性，我们得到。 相同地，。则D是一个正则图。

令，则。否则D有一条哈密顿路，由假设可知产生矛盾。因此

由(1)可得，，则。因为D为G的正则子图，所以对于任意。如果D中存在一条哈密顿路使得它的两个端点u,v是非邻接的，我们有。令为D中的一个哈密顿圈并且假定。现在我们构造。假定并且。我们可以找到一条哈密顿路，对任意的。因此，我们得到一条以为其中一个端点的的哈密顿路。如果，则。在中我们连接，所以我们有。相同地，。因此，对于中的任意一对。由定义可知是一个完全图。由引理2.4，D是哈密顿连通的，也就是说对于D中的每对点，都存在一条以u,v为端点的哈密顿路。因此，对于D中的每对非相邻的点，成立。

现在我们证明主要定理的情形，我们选择k个点不交的4-团和D中一条哈密顿路。

如果，由断言3.2可知，D为一个4-团，设为，从中任选两点，不妨设为。则

因此在H中存在一个4-团，使得，则中至少存在两个不同的点与T中两点相连，设两条关联的边为。因此包含一个哈密顿圈C，且在C中关联的四个点度大于等于4，非关联的点度大于等于3。

如果，D为一个三角形，设为。则

所以在H中存在一个4-团，使得，在中至少存在两个邻点。显然中存在三个不同的点分别为与T中三点相连，对应的边设为。因此包含一个哈密顿圈C，且在C中T中的三个点度大于等于3，中的与关联的三个点度大于等于4，剩余一个点度大于等于3。

如果，这两个点组成路P，设。则

在H中存在一个4-团，使得，则。即P中两点在中的邻点至少有三个为共同点，对应的边组成的集合设为E。因此包含一个哈密顿圈C，且在C中P中的两个点度大于等于4，中的与E中的边关联的三个点度大于等于5，剩余一个点度大于等于4。

如果，D为一个点，设为x。则

在H中至少存在一个4-团，使得。因此包含一个哈密顿圈C，且在C中点的度为4。

当时。令P为D的一条哈密顿路，其中一个端点为u，使得，对于某些。不失一般性，。

由引理2.5，D中有一个4-圈Q使得含有一条起始于u的哈密顿路。因为，所以有一条哈密顿路。 因为D是哈密顿的，我们可以选择在Q与中两条互不相交的边和。我们称有一条从到的支持路。否则，假设。则且。由，则存在，使得。由断言3.2，D是哈密顿连通的，则在与之间存在一条D中的哈密顿路并且是哈密顿的，产生矛盾。用Q代替，则断言3.2对仍成立。那么D是哈密顿连通的，存在一条以和为端点的哈密顿路。因此是哈密顿的，产生矛盾。

现在我们讨论时弦圈C的结构。由定理证明中弦圈C的构造过程可知，包含哈密顿圈，即所构造的弦圈C。在C上中与D中哈密顿路关联的点度大于等于4，其余两点度大于等于3。弦圈C中其它点的度的情况断言3.1已证。□

基金项目

国家自然科学基金资助项目(11671232)。新疆自然科学基金面上项目(2016D01C004)。

文章引用

王怡华,李硕,衣晓宁. 图中具有指定性质的不交子图
Disjoint Subgraphs with Specified Properties in Graphs[J]. 应用数学进展, 2017, 06(02): 139-145. http://dx.doi.org/10.12677/AAM.2017.62016

参考文献 (References)