第３８卷第５期 河南师范大学学报（自然科学版） Ｊｏｕｒｎａｌ ｏｆ Ｈｅｎａｎ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ） Ｚ．３８ Ｎｏ．５ ２０１０年９月 Ｓｅｐｔ．２０１０ 文章编号：１０００—２３６７（２０１０）０５—００２８—０３ 图中具有指定性质的独立４一圈 卢建立，蔡文娟 （河南师范大学数学与信息科学学院，河南新乡４５３００７） 摘 要：主要给出了图Ｇ恰好含有ｓ个Ｋ。和ｋ—ｓ个Ｋ 的最小度条件即：设Ｇ是一个简单图，ｓ，ｋ是两个正 整数且ｓ ｋ，其中Ｇ的顶点个数ｎ三三＝３ｓ＋４（ 一ｓ）＋３，如果Ｇ中任意两个不相邻顶点的最小度之和 ｚ（Ｇ）三三＝ 塑二 或者最小度 （Ｇ） ± ，则Ｇ包含 个顶点不相交的圈ｃ ，Ｃ２￣￣＊Ｃｋ，并且Ｃｉ＝Ｋ。其中１三三三 ｓ， ：Ｋ 其中ｓ＜ｊ ｋ． 关键词：图；独立圈；３一圈；４一圈 中图分类号：Ｏ１５７．５ 文献标志码：Ａ 本文只讨论简单无向有限图．对于一个图Ｇ—Ｇ（Ｖ（Ｇ），Ｅ（Ｇ）），用Ｖ（Ｇ）和Ｅ（Ｇ）分别表示图的顶点集合和边集合．对任 意的ｚ Ｅ Ｖ（Ｇ），用 （ｚ）表示顶点ｚ在Ｇ中的度，ｄ（ｘ，Ｈ）表示ｚ与子图Ｈ之间的边数， （Ｇ）表示图Ｇ的最小度，并定义图Ｇ 中任意两个不相邻的顶点的最小度之和为 （Ｇ）一ｒａｉｎ｛ （ｚ）＋ （ ））｛ｚ， Ｅ （Ｇ）且 Ｅ（Ｇ）｝（若Ｇ是完全图，则令 ｚ（Ｇ）一ｏｏ）． 图Ｇ的任意点Ｕ的邻域表示为Ｎｃ（“）一｛ｚ∈Ｖ（Ｇ）Ｉ—Ｅ Ｅ（Ｇ）｝．对于 （Ｇ）的子集Ｕ，ＧＥｕ］表示由Ｕ导出的子图，图Ｇ的 个独立圈是指Ｇ中ｋ个顶点不相交的圈，４一圈是指长度为４的圈，文中其他未见说明的符号请参看文献Ｉ－１］． 图的独立圈和２一因子问题是图的因子理论中非常重要的一部分，也是图的哈密顿圈理论的推广和延伸．１９６３年Ｃｏｒｒｄｄｉ 和Ｈａｊｎａｌ在文献［２］中给出了一个图Ｇ含ｋ个独立圈的条件是：图Ｇ的顶点数ｎ≥３ｋ，并且 （Ｇ）≥２ｋ；Ｂｒａｎｄｔ等在文献［３］中 给出了Ｇ包含七个顶点不相交的３圈或４圈并且３圈的个数至少是 的条件是：Ｇ的顶点个数 三三＝３ｓ＋４（ｋ— ）＋３，０＂２（Ｇ）≥ ｎ＋ｓ（其中Ｓ ）；颜谨等在文献［４］中改进了文献［３］的结论，得到了Ｇ恰好包含ｋ—Ｓ个４圈的条件．即： 定理Ａ 如果Ｇ是一个简单图，ｓ，ｋ是两个正整数且Ｓ ｋ，其中Ｇ的顶点个数ｎ ３ｓ－Ｆ ４（ 一ｓ）＋３，如果 （Ｇ）三三＝ｎ＋ Ｓ，则Ｇ包含ｋ个顶点不相交的圈Ｃ ，Ｃｚ，…，Ｃ ，并且Ｉ ｃ ｌ＝３其中１ ｉ Ｓ，ｌ ｃ １—４，其中Ｓ＜ｉ≤ｋ． 于潇在文献［５３中得到了Ｇ恰好包含ｋ—Ｓ个带弦４圈（即Ｋ 一ｅ）的最小度条件即： 定理Ｂ 如果Ｇ是一个简单图，５，ｋ是两个正整数且Ｓ ｋ，其中Ｇ的顶点个数ｎ三三＝３ｓ＋４（ｋ一 ）＋３如果０＂２（Ｇ）三三＝ｎ＋２ｋ 一 ，则Ｇ包含 个顶点不相交的圈Ｃ－，Ｃｚ，…，Ｃｋ，并且ｌ Ｃｉ ｌ一３其中１ ｉ ｓ，ｌ Ｃ ｉ＝４且ｌ Ｅ（Ｇ）１ ５其中ｓ＜ｉ 是． 本文受文献［４］和文献［５］的启发得到了图Ｇ恰好含有Ｓ个ｋ。和ｋ～Ｓ个ｋ 的最小度条件即： 定理１ 如果Ｇ是一个简单图，ｓ， 是两个正整数并且５ ，其中Ｇ的顶点个数ｎ≥３ｓ＋４（ｋ一５）＋３，若 ２（Ｇ）≥ 二害 二＿璺或８（Ｇ）≥ －±兰 二 ，则Ｇ包含 个顶点不相交的圈ｃ ，Ｃ２ ９ ｏ ｏ，， ，并且Ｇ—Ｋ。其中】 ｉ ，ｃ，：Ｋ 其 中Ｓ＜ｉ ． １ 引理 引理１ 设Ｃ—ａｌａ２ａ ｓａ４ａｌ是一个４一圈，其中ａｚａ Ｅ Ｅ，若对于任意的 包含一个Ｋ ． ∈Ｖ（Ｃ）有ｅ（ｖ，ｃ）一４，则Ｇ［Ｖ（Ｃ）Ｕ｛ ｝］ 证明 由于 硭 （Ｃ）且ｅ（ｖ，ｃ）：４，则点７３与ｃ上的所有点都相连．易知Ｃ 一啦 ａ２ａ 口足一个Ｋ ． 收稿日期：２００９ １１—３０ 基金项目：河南省杰出青年计划（０８４１００５１００１３） 作者简介：卢建立（１９５３－－），男，河南洛阳人，河南师范大学副教授，研究方向：图论与离散数学 第５期 卢建立等：图中具有指定性质的独立４一圈 ２９ 引理２ 设Ｃ１是一个３一圈，Ｃｚ—ａ】ｎ２ａ３口４ａｌ是一个４一圈，其中ａ２ｎ４∈Ｅ，并且Ｖ（Ｃ１）ｎ （Ｃｚ）：ｐ，若ｅ｛ａ】，ａ３｝，Ｃ１）≥ ５，则包含一个３一圈和一个Ｋ ． 证明 设Ｃｌ：ｚｌ，２７ｚｚ３ｚｌ，当 （｛口ｌ，Ⅱ３），Ｃ ）一６时，则ａｌ和ａ３都与ｃ 中的３个点相连．易知ｃｌ—ａ２吼ａ３ｎ２为一个３一 圈， 一 ａ１．２７２３７ｓｚ 为一个Ｋ ．当Ｐ（｛口 ，ａｓ，Ｃ１｝）一５时，则ａ 和口 中只有一个点与Ｃ 中的３个点全相连，而另一个点只与 ｃ１中的两点相连．不失一般性，设口１与，７２１，３７２，．２７３相连，ｎ３与．３７２，ｚ３相连，易知ｃｌ—ｎ２ａ４口３ａ２为一个３一圈， 一．Ｔｇ１ｎ１．７Ｃ２Ｘ３ｚ１ 为一个Ｋ ． 引理３ 设ｃ１为Ｋ ，Ｃ２一ａｌ口２口。ａ４口１为一个４～圈，其中口２口 ∈Ｅ并且Ｖ（Ｃ１）ｎ （Ｃ２）＝０，若ｅ（Ｃｌ，Ｃ２）三三三１５则ＧＥｖ（ｃ１ Ｕ Ｃ２）］包含两个Ｋ ． 证明 当ｅ（Ｃ１，Ｃ２）一１６时，结论显然成立．当ｅ（Ｃ１，Ｃ２）一１５时，设Ｃ１—３２ｌｚ２ｚ３ｚ４Ｘ１，因ｅ（Ｃ１，Ｃ２）一１５则Ｃ１和ｃ２的 各个顶点之问只有一对顶点没有连边，而这对不相邻点只有两种可能：（１）ｃ 中的某一点与Ｃ２中的ｎ 或ａ 不相邻，不失一般 性，设ｚ２ａ２旺Ｅ，则ＧＥＶ（Ｃ。Ｕ Ｃｚ）］中ｚ１－ｚ２口 口 ｚ１为Ｋ 且ｘ３ｚ４ａ 。２ｚ。也为Ｋ ；（２）ｃ 中的某一点与Ｃ２中的ａ１或ａ３不相邻， 不失一般性，设ｚ２ｎｌ Ｅ，则ＧＥＶ（Ｃｌ Ｕ Ｃ２）］中ｚ２ａ２ａ３口４＿ｚ２为Ｋ４且ｘｌｚ４ｘ３ａｌｚ１也为Ｋ４． 引理４ 设Ｃ ，Ｃｚ是两个独立的４一圈且Ｉ Ｅ（Ｇ）ｌ一５（ 一１，２），若ｅ（Ｃ ，Ｃｚ） １４则ＧＥＶ（Ｃ Ｕ Ｃ ）］包含两个独立的 ４一圈Ｃ 和 并且Ｉ Ｅ（ ）ｌ三三＝５（ 一１，２）其中至少有一个是Ｋ ． 证明 设Ｃ】一３２ｌｚ２ｚ３ｚ４ｚ１，其中ｚ２３２４∈Ｅ．Ｃ２一ａ１ａ２口３ａ４口ｌ，其中＆２口４∈Ｅ．只需证明当ｅ（Ｃ１，Ｃｚ）一１４时结论成立即 可．当ｅ（Ｃ ，Ｃ。）一１４时，按ｃ。中各顶点与ｃ 连的边数分情况进行讨论： 情况１ Ｃ 中有３个点与Ｃ２都连４条边，有一个点与 连两条边，则Ｃ２中各点与ｃ 的连边情况一定是有两个点与Ｃ 连４条边，另两个点与ｃ 连３条边． 情况１．１ Ｃ２中两个与Ｃ。连３条边的点为不邻点，即Ｎ （。 ）＝Ｎ （。。）一３则Ｎ （ｎ ）一Ｎ。（ｎ ）一４．当Ｎ 。（ｚ ）一 ２时（当 （ ２）一２时，情况相似），显然ｚ 只与Ｃ２中的ａ２和口 相连，易知ｚｌ ３２２ｎ ａ２ｚ１为Ｋ ，而ｘ３ｚ４ａ ｎ３ｘ３为一个带一条 弦的４一圈（如图ｌａ）．当 （ｚ ）一２时（当Ｎ 。（ｚ。）一２时，情况相似），显然ｚ－只与Ｃ２中的ｎ。和ａ 相连，则易知ｚｓ ａ ａｚｚ。 为 ，而 ｚ ａ。ｎ ｚ 为带一条弦的４一圈（如图１ｂ）． 情况１．２ ｃ 中两个与ｃ 连３条边的点为相邻点且不是口 和口 ，不妨设Ｎ ．（口。）：Ｎ ，（ｎ ）一３则Ｎ （ｎ ）一Ｎ ，（口 ） 一４．当Ｍ。（ｚ ）一２时（当Ｎ Ｃｒ ）一２时情况相似），显然ｚ 只与 中的ｎｚ和ｎ 相连，则易知３７。Ｘ ｎ ａｚｚ。为Ｋｄ，而 ｚ ｚ２ａ。ａ ｚ 也为Ｋ （如图ｌｃ）．当Ｎ （ｚ ）一２时（当 （ｚ。）一２时，情况相似），显然ｚ 只与Ｃ２中的ａ２和ａ 相连，则易知 ｚｌｚ２ａ１ａ２ｚｌ为Ｋ４，而ｚ３ｚ４ａ４ａ３工３为Ｋ４（如图ｌｄ）． ｔ 情况１．３ Ｃｚ中两个与ｃ 连３条边的点为ａ２和ｎ ，则有Ｍ （＆２）一Ｎ （口 ）一３且Ｎｃ （ａ１）一Ｎ （口。）一４．当 ，（－ｚ ） 一２时（当Ｎ （ ）一２时情况相似），易知ｚ ｚ ａ。ａ ｚ 为Ｋ ，而ｚ ｘ。ａ ａ。ｚ 为带一条弦的４一圈（如图ｌｅ）．当 。（ｚ ）一２时 （当Ｎｒ （ｚ３）＝２时情况相似），易知ｚｌｚ２ａ２口ｌｘｌ为带一条弦的４一圈，而ｏｚ＇。ｚ４ａ ａ。ｚ。为Ｋ （如图Ｉｆ）． 情况２ Ｃ 中有两点与Ｃ２中都连４条边，另两点分别与Ｃ。连３条边．则Ｃ２中各点与Ｃ 的连边情况有两种，其中一种的 证明与情况１相同，另一种是Ｃ２中有两点与Ｃ 中的４点都相连，另两点分别与Ｃ－连３条边，对这种情况进行分类讨论． 情况２．１ Ｃ 中两个与ｃ 连３条边的点为不邻点，即 （口 ）一Ｎ （ｎ。）一３则 （砚）一Ｎ｜１（口 ）一４．则日 与ａｓ在 ｃ 中的公共邻点一定有两个，它们共有６种可能即３２ 与ｚ ，ｚ 与３２。，ｚ 与ｚ ，ｚｚ与３２ ，ｚｚ与－ｚ ，ｚ 与ｚ ．易证在这几种可能 下结论都成立．只任取其中一种进行验证其余类似，不妨取 与ｚ。，并设ｎ ｚｚ∈Ｅ，ｄ。 ∈Ｅ则在Ｇ［Ｖ（ＣＩ Ｕ Ｃｚ）］中 ｚ１ ２ｎ２ａｌｚ１为Ｋ４而且ｚ３ｚ４口４ａ３ｚ３也为Ｋ４（如图ｌｇ）． 情况２．２ Ｃ 中两个与Ｃ 连３条边的点为相邻点且不是口２和ａ ，不妨设Ｎ１（ａ ３）一Ｎｑ（ａ４）一２则Ｎｆ１（ａ１）一Ｎ （ａｚ） 一４，且口４与ｎ。在Ｃｌ中的公共邻点一定有两个，它们共有６种可能即ｚ１与Ｘ２，３７１与ｚ３，ｚ１与 ，ｚ２与Ｘ４，Ｘ２与Ｘ３，Ｘ３与Ｘ４． 不妨取ｚ１与ｚ３，并设ａ４ｚ２∈Ｅ，口３ ４∈Ｅ则在ＧＥｖ（ｃｌ Ｕ Ｃｚ）］中３２１ｚ２口１ａ４ｚｌ为Ｋ４而且ｚ３ ４ａ２ａ３ｚ３也为Ｋ４（如图ｌｈ）．易 证在其余几种可能下结论也都成立． 情况２．３ Ｃ２中两个与Ｃｌ连３条边的点为ａ２和ａ ，则有 （。２）一Ｎｑ（口４）一３且 （ａ１）＝Ｎｃ （ａ３）＝４，ｎ４与ａ２在 Ｃ 中的公共邻点一定有两个，它们共有６种可能即ｚ 与ｚ ，ｚ。与ｚ。，ｚ 与ｚ ，ｚｚ与ｚ ，ｚｚ与ｚ。，ｚ。与Ｘ ．不妨取Ｘｌ与Ｘ３，并 设ｎ 勋∈Ｅ，口２矗∈Ｅ则在￣Ｅｖ（ｃ１ Ｕ Ｃ２）］中ｚ１ ａ３ａ ｚ１为Ｋ 而且ｚ。－ｚ ａ ａｚｚ。也为Ｋ （如图¨）．类似的在其余几种可能 下结论也都成立． ２ 定理１的证明 由定理Ｂ知，Ｇ包含ｋ个顶点不相交的圈Ｃ ，Ｃ ，…， ，并且』Ｃ Ｉ＝３其中１ ｉ ｓ，ｌ ｌ＝４，Ｉ Ｅ（Ｇ）『 ５其中ｓ＜ ｋ．取ｋ个独立圈，满足上述条件并使得： ｋ—Ｓ个４圈中含Ｋ 的个数最多． （＊） ３０ 河南师范大学学报（自然科学版） ２０１０丘 ＸＩ－Ｘ ４ ａ２ ａ２ （ａ） （ｂ） （Ｃ） （ｄ） （ｅ） ７：４ ａ２ 簿 （ｆ） （ｈ） 图１引理４的各种情况示意图 设Ｔ：Ｕ Ｇ，Ｑ ＝Ｕ ｌ； Ｇ，Ｑ２一Ｕ Ｃ （ｓ ｌ ），其中Ｔ是由所有３一圈构成的，Ｑ 中的４一圈都带有一条弦，而 Ｑ 中的４一圈都为Ｋ ．再设Ｈ—Ｔ Ｕ Ｑ。Ｕ Ｑ ，Ｄ—Ｇ— （Ｈ）且ｌ Ｄ Ｉ—ｄ易知 一３ｓ＋４（ｋ—ｓ）＋ｄ，若ｚ—ｓ则定理成立． 若ｚ＞ｓ，则任取ＱＪ中的一个４一圈Ｃ—ａ１ｎ２ａ。ａ４ａ１，令ａ。ａ４∈Ｅ则ａｌ和ａ。为一对不相邻点． 由引理１可知，对任意口∈ （Ｄ）若ｅ（ｖ，ｃ）＝４则ＧＥＶ（Ｃ）Ｕ｛ｖ｝３包含一个ｃ 为Ｋ ．用ｃ 代替ｃ则与（＊）矛盾！从而 ｅ（ｖ，Ｃ） ３即Ｐ（Ｄ，Ｃ） ３ｄ． 由引理２可知，对任意Ｇ ，ｆ当ｅ（｛ｎ ，口 ｝，Ｃ１） ５时，Ｇ［Ｖ（Ｃ Ｕ Ｃｉ）］包含一个３一圈ｃ 和一个４一圈Ｃ 为Ｋ ，用 和 分别代替Ｃ 和Ｃ，则与（＊）矛盾！从而 （｛ａ ，ａ。），Ｃ ） ４则Ｐ（Ｇ，ｃ） １Ｏ，即ｅ（｛ａ ，ａａ｝，Ｔ） ４ｓ且ｅ（Ｔ，ｃ） １０ ｓ． 由引理３可知，对任意Ｇ Ｑ ，当ｅ（Ｃ ，ｃ）三三＝１５时，ｏＥｖ（ｃ Ｕ ｃ ）］包含两个Ｋ ，用这两个Ｋ 代替ｃ 和ｃ，则与（＊）矛 盾！故 （Ｇ，Ｃ） １４，即Ｐ（Ｑ２，Ｃ） １４（ 一ｚ）． 由引理４可知，对任意Ｃ Ｑ ，当ｅ（Ｇ，ｃ）≥１４时，ＧＥＶ（Ｃ Ｕ ｃ ）］包含两个４一圈ｃ 和 且１ Ｅ（ ）ｌ三三＝５（ｉ一１，２）其 中至少有一个是Ｋ ，用ｃ 和 代替Ｇ和ｃ与（＊）矛盾！故Ｐ（Ｇ，Ｃ） １３，即 （Ｑ】，Ｃ） １３（ｚ一 —１）． 当 （Ｇ） 二 成立时，有４ａＣｏ） ４．塑± 二 一３ｎ＋２ｋ—ｓ一２但是 ４３（Ｇ） ｄ（ａｊ）＋ｄ（ａｚ）＋ｄ（ａ ）＋ｄ（ａ ）一ｅ（Ｃ，Ｄ）＋ｅ（Ｃ，丁）＋ （Ｃ，ＱＩ）＋ （Ｃ，Ｑ ）＋ ｅ（Ｃ，Ｃ） ３ｄ＋ｌｏｓ＋１４（ 一Ｚ）＋１３（Ｚ— 一１）＋１０—３ｎ＋２ｋ—Ｚ～３ ３ ＋ 一ｓ一３， 显然矛盾！所以此时ｆ＞Ｓ是不成立的．故ｆ一５即定理成立． 当 （Ｇ） 下４ｎ－－３ｓ－－８成立时 （Ｇ）三三二 二 ２（Ｇ） ｄ（ａ１）＋ｄ（ａ３） 一２咒一要 一４但是 ２ｄ＋４ｓ＋８（ 一Ｚ）＋８（Ｚ—Ｓ～１）＋４—２ｎ一２ｓ一４． 显然矛盾！所以此时ｚ＞ 是不成立的．故ｚ—Ｓ即定理成立．定理１证毕． 参 考 文 献 ［１３ Ｂｏｎｄｙ Ｊ Ａ，Ｍｕｒｔｙ ＵＳＲ．Ｇｒａｐｈ Ｔｈｅｏｒｙ ｗｉｔｈ Ａｐｐｌｉｃａｔｉｏｎｓ［Ｍ３．Ａｍｓｔｅｒｄａｍ：Ｎｏｒｔｈ—Ｈｏｌｌａｎｄ，１９７６． ［２］Ｃｏｒｒ＆ｄｉ Ｋ，Ｈａｊｎａｌ Ａ．Ｏｎ ｔｈｅ ｍａｘｉｍａｌ ｎｕｍｂｅｒ ｏｆ ｉｎｄｅｐｅｎｄｅｎｔ ｃｉｒｃｕｉｔｓ ｉｎ ａ ｇｒａｐｈ［Ｊ］．Ａｃｔａ Ｍａｔｈ Ａｃａｄ Ｓｃｉ Ｈｕｎｇ，１９６３，１４：４２３—４３９ ［３３ Ｂｒａｎｄｔ Ｓ，Ｃｈｅｎ Ｇ，ａｕｄｒｅｅ Ｒ Ｆ，ｅｔ ａ１．Ｄｅｇｒｅｅ ｃｏｎｄｉｔｉｏｎｓ ｆｏｒ ２－ｆａｃｔｏｒ￣Ｊ］．Ｊ Ｇｒａｐｈ Ｔｈｅｏｒｙ，１９９７，２４：１６５—１７３． ［４３ Ｙａｎ ｊ．Ｄｉｓｊｏｉｎｔ ｔｒｉａｎｇｌｅ￣ａｎｄ ｑｕａｄｒｉｌａｔｅｒａｌｓ ｉｎ ａ ｇｒａｐｈ［Ｊ３．Ｄｉｓｃｒｅｔｅ Ｍａｔｈ，２００８，３０８：３９３０—３９３７． ［５３于潇．关于图中相互独立的圈和２一因子的新结果［Ｄ］．济南：山东大学，２００８． ［６３付玉娟，蔡焕杰，张旭东．基于图论和列队竞争算法的环状管网优化设计［Ｊ］．灌溉排水学报，２００８，２７（４）：８１—８４ （下转第３３页） 第５期 粱月亮等：一类三点边值问题两个单调递增正解的存在性 ３３ 因此，有 Ｉ ｌ和凹性可由引理１得知，证毕． 【 Ｉｌ Ｉｌｌ， ∈Ｋ ｎ ． （５） 从而由（３）一（５）及引理４可得算子Ｔ存在不动点Ｕ ∈Ｋ（： ＼ ＊），“。∈Ｋ￣２７￣－．＼０ ），“。，“ｚ的单调性 参 考 文 献 ［１］梁月亮，续晓欣．一类三点边值问题单调递增正解的存在性口］．河南理工大学学报：自然科学版，２０１０（３）：４２５—４２９． Ｅ２３续晓欣，梁月亮．二阶三点边值问题两个正解的存在性［Ｊ］．中北大学学报：自然科学版，２００９，３０（２）：１０５—１０９． ［３］姚庆六．一类二阶三点非线性边值问题的正解存在性与多解性ＥＪ３．数学学报，２００２，４５（６）：１０５７—１０６４． Ｅ４３姚庆六．非线性二阶三点边值问题正解的一个存在定理ＥＪ３．系统科学与数学，２００３，２３（４）：４９５—５００． Ｅ５３ Ｈａｎ Ｘｉａｏｌｉｎｇ．Ｐｏｓｉｔｉｖｅ ｓｏ［ｕｔｉｏｎｓ ｏｆ ｆｌ ｔｈｒｅｅ－ｐｏｉｎｔ ｂｏｕｎｄａｒｙ ｖａｌｕｅ ｐｒｏｈｌｅｍ［－１］．Ｊ Ｍａｔｈ Ｒｅｓｅａｒｃｈ Ｅｘｐｏｓｉｔｉｏｎ，２００７，２７（３）：４９７－５０４ ［６］Ｇｕｏ Ｄａｊｕｎ，Ｌａｋｓｈｍｉｋａｎｔｈａｍ Ｖ．Ｎｏｎｌｉｎｅａｒ ｐｒｏｂｌｅｍｓ ｉｎ ａｂｓｔｒａｃｔ ｃｏｎｅｓ ＥＭ］．Ｓａｎ Ｄｉｅｇｏ：Ａｅａｄｅｍｉｃ ｐｒｅｓｓ，１９８８． Ｅｘｉｓｔｅｎｃｅ ｏｆ Ｄｏｕｂｌｅ Ｍｏｎｏｔｏｎｅ Ｉｎｃｒｅａｓｉｎｇ Ｐｏｓｉｔｉｖｅ Ｓｏｌｕｔｉｏｎｓ ｆｏｒ Ｔｈｒｅｅ－Ｐｏｉｎｔ Ｂｏｕｎｄａｒｙ Ｖａｌｕｅ Ｐｒｏｂｌｅｍｓ ＬＩＡＮＧ Ｙｕｅ—ｌｉａｎｇ，ＸＵ Ｘｉａｏ—ｘｉｎ （Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ，Ｎｏｒｔｈ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｃｈｉｎａ，Ｔａｉｙｕａｎ ０３００５１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ａ ｃｌａｓｓ ｏｆ ｎｏｎｌｉｎｅａｒ ｔｈｒｅｅ－ｐｏｉｎｔ ｂｏｕｎｄａｒｙ ｖａｌｕｅ ｐｒｏｂｌｅｍｓ ｉｓ ｃｏｎｓｉｄｅｒｅｄ，ａｎｄ ｔｈｅ ｅｘｉｓｔｅｎｃｅ ｏｆ ｄｏｕｂｌｅ ｍｏｎｏｔｏｎｅ ｉｎｃｒｅａｓｉｎｇ ｐｏｓｉｔｉｖｅ ｓｏｌｕｔｉｏｎｓ ｉｓ ｏｂｔａｉｎｅｄ ｂｙ ｍａｋｉｎｇ ｕｓｅ ｏｆ ｔｈｅ Ｋｒａｓｎｏｓｅｌ＇ｓｋｉｉ ｆｉｘｅｄ ｐｏｉｎｔ ｔｈｅｏｒｅｍ ｏｆ ｃｏｎｅ ｅｘｐａｎ— ｓｉｏｎ－ｃｏｍｐｒｅｓｓｉｏｎｓ ｔｙｐｅ ａｎｄ ｔｈｅ ｐｒｏｐｅｒｔｉｅｓ ｏｆ Ｇｒｅｅｎ ｆｕｎｃｔｉｏｎ，ｔｈｅ ｒｅｓｕｌｔｓ ｇｅｎｅｒａｌｉｚｅ ａｎｄ ｉｍｐｒｏｖｅ ｔｈｅ ｋｎｏｗｎ ｏｎｅｓ． Ｋｅｙ ｗｏｒｄｓ：ｔｈｒｅｅ—ｐｏｉｎｔ ｂｏｕｎｄａｒｙ ｖａｌｕｅ ｐｒｏｂｌｅｍｓ；ｐｏｓｉｔｉｖｅ ｓｏｌｕｔｉｏｎｓ；ｆｉｘｅｄ ｐｏｉｎｔ ｔｈｅｏｒｅｍ ｛上接第３Ｏ页） Ｖｅｒｔｅｘ－ｄｉｓｊ ｏｉｎｔ Ｑｕａｄｒｉｌａｔｅｒａｌｓ Ｃｏｎｔａｉｎｉｎｇ Ｓｐｅｃｉｆｉｅｄ Ｐｒｏｐｅｒｔｉｅｓ ｉｎ ａ Ｇｒａｐｈ ＬＵ Ｊｉａｎ—ｌｉ，ＣＡＩ Ｗｅｎ－ｊ ｕａｎ （Ｃｏｌｌｅｇｅ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ，Ｈｅｎａｎ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉｎｘｉａｎｇ ４５３００７，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｉｓ ｐａｐｅｒ ｇｉｖｅｓ ｔｈｅ ｍｉｎｉｍｕｍ ｄｅｇｒｅｅ ｃｏｎｄｉｔｉｏｎ ｆｏｒ ａ ｓｉｍｐｌｅ ｇｒａｐｈ ｊｕｓｔ ｃｏｎｔａｉｎｉｎｇ ｓ Ｋ ３ ａｎｄ ｋ－－ｓ Ｋ４，ｔｈａｔ ｉｓ： ｓｕｐｐ。ｓｅ ｓ ａｎｄ ｂｅ ｔｗ。ｉｎｔｅｇｅｒｓ ｗｉｔｈ ｓ二三三 ａｎｄ １ｅｔ Ｇ ｂｅ ａ ｓｉｍｐ１ｅ ｇｒａｐｈ ｗｉｔｈ ＩＧＩ＝ 三三＝３ｓ＋４（ —ｓ）＋３，ｉｆ ２（Ｇ）三三＝ 二 二 。ｒ （Ｇ）三三三 ± ≤ ． ，ｔｈｅｎ Ｇ ｃｏｎｔａｉｎｓ矗Ｖｅｒｔｅｘ－ｄｉｓｊ。ｉｎｔ ｃｙｃｌｅｓ ｃ１，Ｃ２，…， ｓｕｃｈ ｔｈａｔ Ｇ—Ｋ３ ｆ。ｒ ｌ ｓ ａｎｄ ＣＪ—Ｋ４ ｆｏｒ ｓ＜ Ｋｅｙ ｗｏｒｄｓ：ｇｒａｐｈ；ｄｉｓｊｏｉｎｔ ｃｙｃｌｅ；ｔｒｉａｎｇｌｅ；ｑｕａｄｒｉｌａｔｅｒａｌ