ABSTRACT

Let G be a graph of order n with, where k is a positive integer. Suppose that, then G contains k independent quadrilaterals.

Keywords:Vertex-Disjoint, Cycle, Quadrilaterals

图中点不交的4-圈

衣晓宁，颜谨

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

收稿日期：2016年7月28日；录用日期：2016年8月18日；发布日期：2016年8月25日

摘 要

令G是一个顶点数为n的图，满足，k是任意正整数。假设，则图G包含k个独立的4-圈。

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

1. 引言

本文中的图都为简单图。令是一个简单图。图的顶点数和边数分别为和。图的一系列子图称为独立的如果任意两个子图在中没有公共点。令和是的子图。如果和在中没有公共点，我们定义为和之间的边数。令是的子图并且，表示在中的邻点。令。对中子图，令，且表示的导出子图。表示图的最小度，同时我们定义

。

我们使用和表示分别顶点数为的圈和路。而且表示圈中弦的个数。对于任意子图，我们用符号是表示是最优的，如果任意中子图，满足。和分别表示圈和路的长度，即和。

令是顶点数为5的包含两个边不交三角形的图，的中心点是度为4的点。令是顶点数为5，由删除一条与中心点相连的边获得的图。

图的哈密顿圈问题是图论研究中最著名的问题之一。而图中包含指定长度的圈问题则是哈密顿圈问题的延伸。1963年，Corrádi和Hajnal给出了如下结论。

定理1 [1] 设是一个顶点为的图。如果并且，那含有个点不交的圈。

在2004年，文章 [2] 证明了定理：

定理2 [2] 设是一个顶点为的图，满足，为正整数。假设，那含有个独立的4-圈。

本文对定理2的度条件加以改进，得到如下命题。

定理3 设是一个顶点为的图，满足， 为正整数。假设，那含有个独立的4-圈。

其它相关结果在 [3] - [5] 中有介绍。同时文中其它未见说明的符号请参见 [6] 。

2. 引理

令是一个顶点数为的图，满足。为了证明，我们先使用如下引理。

引理1 [2] 令和是图中两个相互独立的圈，满足，，和是最优的。假设，则存在和，使得，对任意成立，。同时，如果则。

引理2 [2] 令，和是图中三个相互独立的圈，满足，和，并且使得是最优的。令和，它们满足，对所有成立，并且。假设不包含和。则存在满足，，和。

引理3 [3] 令和是图中相互独立的两条路，满足和。如果，则包含一个4-圈。

引理4 [2] 令和是图中四个相互独立的圈，满足，，并且使得是最优的。令，和。满足，和，同时成立对任意，，和。假设不包含和，则存在和满足，，，和。

引理5 [2] 令和是图中五个相互独立的圈，满足和，而且使得是最优的。令，，，和。假设，和，满足对任意，和，，，，。则。

引理6 [2] 令和是图中两个相互独立子图，满足和。令是的中心点。如果，则。

引理7 [3] 令是图中一个4-圈。令和是中两个不相连的点。如果，则包含一个4-圈和一条边满足和是相互独立的，并且是与或相连的。

引理8 [2] 令和是图中两个相互独立的子图，满足和。令是的中心点。假设，是最优的，并且不包含，和。则图存在和，满足，，，和。

引理9 [2] 令和是图中三个相互独立的子图，满足和。令和，能够满足，，，，以及。假设不包含，和。则存在，满足，，，和对某一，并且如果则，如果则。

3. 定理的证明

令是一个顶点数为的图，满足和，其中是一个正整数。假设不含个独立的4-圈。我们假设对任意一对不相连的点和。令，则。为了证明，我们先证明下列断言。

断言1。

证明：假设，满足。令和是的中心点。容易看出否则。因为，，则。这表明存在4-圈满足。根据引理6，，矛盾。

根据图的选择，包含个独立4-圈。令为个4-圈。我们断言。反之，假设有个独立4-圈，满足含有一条阶为 的路。我们选择和使得尽可能大。令，和。因此。令满足。令。由于，我们可以知道。所以。因为，则。这表明存在4-圈，不失一般性设，满足。根据断言2 [2] ，同样可以得到如下结论：

断言2 图包含个独立4-圈，满足含有一条阶为5的路。

我们选择个独立4-圈，使得含有一条阶为5的路。并且在此基础上，令尽可能大。我们断言含有一个子图满足和。假设。令。令，和。则我们有。因为，则，设。因为，，所以。根据断言3 [2] ，可以获得如下结论：

断言3 存在个独立4-圈，使得含有一个阶为5，边数至少是5的子图。

断言4。

证明：根据断言3，存在个独立4-圈，使得含有一个阶为5，边数至少是5的子图。令和。如果，令和是的两个不同端点。则，否则或者。因为，因此。我们可以假设。根据引理7，满足恰有一点和是的端点。因此。所以，我们选择和，使得和尽可能大。

令。因为不含和，我们可知如果对，则。因此，并且因为和，所以。我们可以假设。根据引理8，令，满足，，，和，。因此

。

令。显然，，否则。因此我们看出。所以，

。

因为，所以。如果，则因为，，。如果，则因为，，。因此。我们可以假设。根据引理9，我们一定有，。令，满足，。不失一般性，我们假设和。令，，和。显然，和。很容易验证否则，。因此和否则，的中心点是。总之，。我们可以假设。根据引理7，设存在一个点满足和，使得。所以满足，矛盾。断言成立。

断言5 存在个独立的4-圈和满足，使得包含一条顶点数为的路。

证明：根据断言4，我们选择和使得包含一条最长的路。在此基础上，令尽可能大。假设。则。令满足如果有一条边是。因此。由于，我们可得对所有的成立。因为所以。我们假设。根据引理7，，因此必然有。令。首先假设，不失一般性说。则因为。所以，矛盾。

假设和。令。则和，否则。注意到，我们假设。可以断言。否则，则因为和。这表明和。我们有并且，矛盾。因此。由于，我们看出。这很容易看出因为。则因为。我们可以假设。令。相似地，我们可以假设和。所以。断言成立。

根据断言5，令满足和，使得尽可能大。很容易得到否则。令。我们可以得到因为，和。我们假设。取。则不包含和。令。根据引理1，假设，对任意，并且。令。

我们断言存在满足。假设断言不成立，显然。当，因为，，则。我们假设存在满足。因此我们假设。根据断言6 [2] ，。令和。则。我们可以得到因为。如果，则因为，，。如果，则因为，，。因此。根据断言6 [2] ，下列断言成立：

断言6 存在满足。

根据断言6，我们假设。令。根据引理2，令满足，，和。再令，，，并且对。

取。根据，我们假设，同时令和，满足和对某一和。我们已知对。如果，则，矛盾。则，因此。我们可以得到。

断言7，对和。

证明：首先，假设对某一。显然可以得到，矛盾。因此对任意。接下来，假设对某一。如果对某一，则，矛盾。因此，同时类似的，。则，并且，矛盾。因此对任意。最后，假设。设对某一。如果，令根据引理3。所以，矛盾。因此。则因为我们假设。这表明，并且对。因此，矛盾。因此断言成立。

根据断言7，我们知道，和。由于不包含，我们有和。如果，则对，和。如果，则对，和。因此

。

不失一般性，我们假设。根据引理4，令和，能够满足，，，，。

令和。由于，我们有。我们可以估计。我们已知。如果，则对某一。因此，矛盾。因此和。如果对，则，矛盾。得到。所以。并且。由于不包含和，我们有和，设。显然，表明

。

我们可以假设。根据引理5，。定理证明完毕。

基金项目

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

文章引用

衣晓宁,颜谨. 图中点不交的4-圈
Vertex Disjoint Quadrilaterals in Graph[J]. 应用数学进展, 2016, 05(03): 399-405. http://dx.doi.org/10.12677/AAM.2016.53049

参考文献 (References)