《图中存在独立圈及指定条件因子的度条件》由会员分享，可在线阅读，更多相关《图中存在独立圈及指定条件因子的度条件（109页珍藏版）》请在金锄头文库上搜索。
1、山东大学 博士学位论文 图中存在独立圈及指定条件因子的度条件 姓名：高云澍 申请学位级别：博士 专业：运筹学与控制论 指导教师：李国君 20090330 山东大学博士学位论文 图中存在独立圈及指定条件因子的度条件 高云澍 山东大学数学学院 运筹学与控制论 摘要 图论的研究始于2 0 0 多年前关于图论的第一篇论文是1 7 3 6 年E u l e r 发表的， 他用图的方法解决了哥尼斯堡( K j n i g s b e r g ) 七桥问题二十世纪六十年代以来，图 论在科学界异军突起，活跃非凡图论中有很多著名的问题，如哈密尔顿间题，四 色问题，中国邮递员问题等并且，应用图论来解决化学，计算机
2、科学，生物学等 学科问题已显示出极大的优越性图论作为离散数学的一个重要分支，受到了各 方面的普遍重视 本文考虑简单有限图，这些图不包含环以及重边设G 表示一个简单图哈 密尔顿圈问题是图论中非常著名的问题之一图中过每个顶点的圈，称为图的 哈密尔顿圈图的哈密尔顿圈问题，是图论中的一个非常著名的间题图G 中 的k 因子指的是图G 中的k 正则子图，这里k 是一个正整数关于k 一因子的存在性， 应用T u t t e 的定理，人们得至I J 了许多有意义的结果，然而，在本论文中，我们主要关 注2 一因子的存在性显然，一个哈密尔顿圈可以被看成是仅有一个分支的2 因子 因此，对于给定的图，找到2 一因子存
3、在性的条件是很困难的过程常用的技巧是先 找出一个顶点数目极小的包装，然后扩充成为2 因子 本文研究了图论中的几个问题，具体地，我们研究了包含哈密尔顿圈的k 一因 子存在性问题，图G 中相互独立的子图( 特别是圈) 以及2 一因子的存在性条件上述 问题可以概括地描述如下：设F 是具有给定结构的连通子图，七是一个正整数，保 证顶点数目满足I V ( G ) I k l V ( F ) I 的图G 中包含k 个点不相交的F 存在的最小度条件 或者不邻接的最小度和条件是多少? 上述问题是极值图论中的很基本的问题对 于非完全图G ，定义c r 2 ( G ) ：= m i n d G ( x ) - I
4、 - 如t y ) l x y 譬E ( G ) ) ；如果G 是一个完全图， 令c r 2 ( G ) ：= 全文共分为八章第一章，我们给出了一个简短而又相对完整的 引言首先，我们给出了一些基本的术语和定义然后，我们介绍了2 一因子理论及 独立圈理论的背景和进展最后，我们列出了本文的主要结果 山东大学博士学位论文 在第二章，我们给出了包含哈密尔顿圈的k 因子的度条件设k 为满足k 2 的 正整数，并且设图G 的定点数目n 足够大如果砌为偶数，图G 中的最小度至少 为k 并且m a x d 6 ( x ) ，如( ) ，) l ( r t + a ) 2 对每一对不相邻接的工和Y 都成立，这里
5、， 当k 为奇数时，口= 3 当k 为偶数时，口= 4 我们证明了图G 中存在一个k 因子( 亦 即七一正则子图) 包含任意给定的哈密尔顿圈C ，只要G E ( C ) 是连通的通过构造 例子，我们同时说明了度条件是最好可能的以及连通条件是必须的 在第三章，我们考虑二分图G 中存在2 一因子的度条件使得2 因子的每一个分 支为长为4 的圈并且刚好包含一个指定的顶点首先，我们找到了二分图G 的一个 包装，使得每一个分支或者为长为4 的圈，或者为长为6 的圈，然后我们把包装拓展 为需要的2 因子我们的主要结果如下：设k 是一个正整数并且G = ( n ，屹；E ) 是 一个二分图，其中l V l
6、I = l v 2 I = n 2 k - I - 2 如果如( 力+ 如l 华l 对于每 一对顶点X V l 和Y V 2 都成立，则对于图G 中任意的k 个不相同顶点z l Z k ， 图G 中存在一个2 因子包含k + 1 个相互独立的圈C l ，G + l 使得对于每一 个f l ，k ) ，Z i y ( C i ) 并且I C i l = 4 在第四章，我们探索存在2 因子存在的c r 2 ( G ) 条件，使得2 因子每一个分 支为带弦的4 圈事实上，我们证明了如果图G 的阶数r 4 七+ 3 并且0 r 2 ( G ) n + k ，, 贝I J G 中存在2 因子包含k +
7、1 个相互独立的圈C l ，Q + l ，使得对于每一 个f ( I ，k 一1 ，C i 为带弦的4 圈且I C k I 4 紧接着，我们证明了如果图G 的 阶数n 4 k 并且旷2 ( G ) n + k ，则G 存在2 一因子包含k 个相互独立的圈使得其中 的k 一1 个为带弦的4 圈与此同时，我们证明了阶数条件以及c r 2 ( G ) 条件都是最好 可能的 在第五章，我们考虑了关于相互独立的三角形和四边形的包装问题对于 阶数n 3 s + 4 ( k J ) 图G ，其中s 是两个正整数k 使得1 s 毛我们证明了如 果矿2 ( G ) n + s ，则图G 包含k 个相互独立的圈C
8、 l ，c 七，使得对于1 4 k 并且o r 2 ( G ) n + k 则G 中存在2 因 子包含七个相互独立的圈使得其中的k 1 个为带弦的四边形 在第五章，我们感兴趣的是图中相互独立的三角形以及四边形的存在性，我 们的结果如下 定理5 3 设s 和k 为两个整数使得1 s k 如果阶数为n 3 s + 4 ( k s ) 的图G 满 足c r 2 ( G ) n + s , 贝t J G 包含k 个相互独立的圈C l ，G ，使得对于1 i S ，I C i I = 3 ； 对于5 8 k 2 2 + 1 2 ) k + 3 a + 1 6 的 图，其中，当七为奇数时口= 3 ；当七为
9、偶数时口= 4 如果加为偶数，6 ( G ) 忌并 - 臣c r 2 ( G ) n + 口则G 中存在k 一因子包含给定的哈密尔顿圈 在本章中，我们改进了定理2 5 定理2 6 ：设足2 为整数，G 为阶数n 1 2 ( k 一2 ) 2 + 2 ( 5 一o ) ( 足一2 ) 一口的图，其中， 当七为奇数时口= 3 ；当七为偶数时口= 4 如果砌为偶数，6 ( G ) 忌并且对G 中每一对 不相邻的顶老u C w v ，m a x d ( x ) ，d ( y ) l 伽+ a ) 2 则G 中存在k - 因子包含给定的哈密 尔顿圈C 只要G E ( C ) 是连通的 本章主要结果发表在
10、D i s c r e t eM a t h e m a t i c s ，3 0 9 ( 2 0 0 9 ) 2 3 7 3 2 3 8 1 7 山东大学博士学位论文 2 2 主要结果 为了得到主要结果，我们首先给出T u t t e 的确保图中存在k 一因子的定理 定理2 7 ：( T u t t e 【7 2 1 ) 设G 为图忌1 为整数则图G 包钒一因子当且仅当 o c ( s ，T ，J i ；：) = J i = I s l + ( d G - s ( 曲- k ) - h G ( s ，T ，七) 0 r E r 对于y ( G ) 的所有点不相交的子集和s 和丁都成立，这里
11、G ( S ，L 七) 表示G 一( S u 丁) 中 的分支D 的数目，使得k i D l + e G ( y ( D ) ，T ) 兰1 ( m o d2 ) 另外，不管G 中是否有k - 因 子，对于y ( G ) 的所有点不相交的子集和s 和丁，我们始终有钻( S ，T ，k ) 三k I V ( G ) I ( m o d2 ) 我们称上述定理中的分支D 为奇分支令t o ( G ) 表示图G 的分支数并且 令D ( G ) 表示图G 中含有奇数阶数的分支个数我们先给出几个命题 命题1 如果定理2 6 的条件是满足的，k 3 并且对于G 中的任意哈密尔顿 圈C ，G E ( C )
12、是连通图则对于ACy ( G ) ，t o ( G E ( C ) 一A ) I A I + 1 ，除非七= 3 并且G 中存在3 一因子包含C 证明：令H ：= G E ( C ) 假设存在Acy ( G ) 使得t o ( H A ) I A l + 2 如果A = 0 ， 显然矛盾因此，不妨i L 4 O 令C l ，c 2 ，C 甜为H A 的分支不失一般性，不 妨i 殳1 C l I I C 2 I l e l 由于H 是连通图并且根据假设，山2 ，因此存在 点置v ( c f ) 使得N ( x i ) n A O ，这里f 1 ，2 ，u ) 我们断言粗在工f ，X I X l
13、，x 2 ，X I A I + I l 使得工，和殉是不相邻的要不然，我们 不妨设在圈C 中，v ( c 1 ) 中的所有点跟y ( C 2 ) 的点都相邻并且I c l I I C 2 l 2 如 果I A I 2 ，贝, l t o ( n A ) 4 如果I C 2 I = 2 ，则对于U l y ( C 1 ) ，e c ( u l ，y ( C 2 ) ) = 2 并 且对U 3 y ( C 3 ) ，H 1U 3 岳E ( G ) 如果I C 2 I _ 1 ，今l u ll = V ( C O r X 及l u ：) - - y ( C 2 ) ， N u l U 2 E ( G
14、 ) 因此，存在U 3 v ( c 3 ) 使得U l U 3 叠E ( C ) 或者U 2 U 3 叠E ( C ) 从而， 只需考虑I A l = l 并且u ( 日一A ) = 3 显然，I C I I = 1 并且I C 2 I 2 ，记A = z ) 如 果I C 2 I = 1 ，则y ( C 2 ) = x 2 根据X l 和x 2 的对称性，沿着圈c ，存在两种类型的结构， 分别见图1 和图2 ，这E v ( c 3 ) = v ( P ) U “1 如果I C 2 l = 2 ，i e - , V ( C 2 ) = X 2 ，) 因此， 根据z E ( G ) 或者z 莹E
15、 ( G ) ，存在三种类型的结构，这E V ( C 3 ) = v ( P ) U H ) ， 8 山东大学博士学位论文 Z 图2 1 T y p e1 Z 图2 2 T y p e2 见图3 注意到在每一种情况下，由于如( 工1 ) = 3 ，则七= 3 ，此时口= 3 另 外，注意到型2 不会出现由于n 是偶数，则对于每一对不相邻的点w l ，W 2 y ( 娜，m a x l d H ( w 1 ) ，d H ( w 2 ) 墨，由定理2 2 ，G E ( c ) 包含哈密尔顿圈，于是G 包 含两条边不相交的哈密尔顿囹由于，l 是偶数，G 一层( C ) 包含I 因子，记为厂则， E ( C ) u 厂构成了3 一因子使得其包含C Z 图2 3T y p eI X Z 图2 5T y p e2 c 3 五 9 Z 图2 4B p eI 山东大学博士学位论文 由上面的断言以及定理2 6 的条件，不妨设_ ，在日中的最小度至少；碧jn + t 。r - 4 从而 掣妇( 巧) I V ( C j ) l 一1 + I A I 于是，对于每一个i 工都有 I v ( G ) I 掣一陋l + 1 考虑到j 陋I + 1 t ,
