《图中强路圈性质的若干充分条件》由会员分享，可在线阅读，更多相关《图中强路圈性质的若干充分条件（47页珍藏版）》请在金锄头文库上搜索。
1、山东师范大学 硕士学位论文 图中强路圈性质的若干充分条件 姓名：程建民 申请学位级别：硕士 专业：应用数学 指导教师：王江鲁 20090402 【l 农师范火学硕士学毖论文 图中强路固性质的若干充分条件 程建民 ( 山东师范大学数学科学学院济南，山东，2 5 0 0 1 4 ) 中文摘要 图的路和圈问题是图论中个十分重要而且活跃的研究课题，有大量的实际问 题可以归结为图的路和圈问题图论中三大著名难题之一的H a m i l t o n 问题本质上 也是图的路和圈问题国内外许多学者对此问题作了大量的研究工作这方面的研 究成果和进展可参见文献f 3 s 一 4 2 1 其中度条件和邻域并条件成为研
2、究路和圈问题 的重要途径，在这方面取得了很多优秀的成果经过几十年的发展，图的路圈性质所 涉及的内容日益丰富和具体路的方面包括图的H a m i l t o n 路( 可迹性) ：齐次可迹 性，最长路，H a m i l t o n 连通，泛连通，路可扩等等；圈的方面包括图的H a m i l t o n 圈， 最长圈，( 点) 泛圈，完全圈可扩，点不交的圈，圈覆盖等等 由于直接研究般图的H a m i l t o n 问题往往比较困难，于是人们转而研究不含 有某些禁用子图的图类继B e i n e k e l 9 7 0 年发表的关于线图性质的文章【1 7 之后， 人们开始关注包含着线图的无爪
3、图7 0 年代末8 0 年代初，是研究无爪图的一个非 常活跃的时期关于无爪图方面的部分优秀成果可参考【1 】【3 ，【1 9 】- 【3 1J 另外，无爪 图的概念也被从不同角度推广到了更大的图类，半无爪图，几乎无爪图，( K 1 ，4 ；2 ) 一图 等2 0 0 5 年，刘春房在【4 】中定义了一种新的图类_ 【s ，t 卜图，即任意s 个点之间至 少含有t 条边而我在这类b 牛图的基础上提出了强一【s ，t 图，即任意s 个点之间 至少含有t 条独立边这类图的特点是其边的分布比较均匀，因而在交通网络，通信 系统，计算机的网络配置等方面有着很典型的应用 本文就是研究强一 s t 图和一般图
4、中与度有关的强路圈性质 在第一章中，我们主要介绍文章中所涉及的一些概念和术语符号，以及本文的 研究背景和已有的一些结果 在第二章中，我们主要研究了强一【s ，t 】图在不同条件下的强路圈性质，得到下面 的结果： 定理2 1 4 设G 是n ( n 6 ) 阶强一【4 ，2 】图，则G 是泛圈的 定理2 1 5 设G 是n ( n 7 ) 阶强一【4 ，2 】图，则G 是完全圈可扩的 1 山东师范大学硕：t 学位论文 定理2 1 6 设G 是7 1 ( r 1 三= 8 ) 阶强一【4 ：2 】图，则G 是路可扩的 定理2 2 4 设G 是n ( n28 ) 阶连通强一f 5 ，2 J 图，则G
5、 含有H a m i l t o n 路 定理2 2 5 设G 是6 ( G ) 3 的连通? 局部连通的强- 【5 ，2 】图，则C 是完全圈 可扩的或者同构于图P 推论2 2 6 设G 是d ( G ) 芝3 的“ 8 ) 阶连通，局部连通的强一 5 ，2 】图，则 G 是完全圈可扩的 定理2 3 3 设G 是n ( n 3 m 一1 ) 阶强一 2 m ，叫图，则G 含有H a m i l t o n 路 定理2 3 4 设G 是n ( n23 m ) 阶强 2 m ，叫图，则G 含有H a m i l t o n 圈 在第三章中，讨论了图中在与度有关的条件下关于圈的几个结果： 定理3
6、8 设G 的阶礼3 ，如果G 中任意一对不相邻的顶点u ，“ 满足d ( u ) - 4 - d ( v ) 礼+ 惫，则G 中任意个满足彘 5 此时C = V l U 2 仇仇一l 仇不失一般性，可假设l v i C v t I 5 ，其中i 2 考虑C x ，V 2 ，0 i + 1 ，u 七一1 ，“ 七】，1 1 2 ，3 7 f i + 1 ，岔1 堰一1 ，T , 1 1 k 萑E ( G ) 若“ v 2 v k 一1 ，U i + l U k E ( G ) ，则可得z u l V k U i 十1 一C u k l V 2 C u i x 为扩圈所以V 2 Y k ，V i
7、+ V k 一1 E ( G ) 考 虑C x ，U 2 jU i + l ，仇一2 ，仇一1 】，X Y 2 ，z 忱+ 1 ，x v k 一2 ，X U k 一1 芒E ( G ) 若U 2 U k - 1 ，v i + l v k 一2 E ( G ) ，则可得z u l V k V k l 仇+ 1 C V k 一2 U 2 C U i X 为扩圈所以V 2 “ U k 一2 ，“ O i + l U k 一2 E ( G ) 2 0 山东师范大学硕士学位论文 由此可得；I ： U I U k V i + 1 C v k 一2 c 2 C v i x 为扩圈，矛盾 综上，定理2 2 5
8、 得证 推论2 2 6 设G 是石( G ) 3 的n ( n 8 ) 阶连通，局部连通的强一 5 ，2 】图j 则 G 是完全圈可扩的 2 3 强- 2 m ，仇 图的路圈性质 本节主要选取强一 2 m ，m 】图作为研究对象，得到 定理2 3 3 设G 是n ( n 3 m 一1 ) 阶强一 2 m ，m 】图，则G 含有H a m i l t o n 路 定理中n23 m 一1 的条件是必要的 证明：选取G 中的条最长路P = u 1 V 2 若P 不是H a m i l t o n 路，则 在G P 中任意选取一个分支日G 的阶竹3 m 一1 ，由引理2 1 3 可知，G 是 m 一1
9、 连通的由此可得I N p ( H ) l2m 一1 将、r P ( 日) 中的顶点按照在尸上的顺序 记为X l ，X 2 ，z t ( 1 m 1 ) 在日中与之邻接的顶点为耖1 ，沈，Y l ，显然对于 i j ( 1 i ，J z ) ，玑可以为珊在日中任意选取个顶点z ，显然Z V l 隹E ( G ) 若z z E ( G ) ( 1 i f ) ，则可得V l P x i y i H z x + P v k 为更长路其中y i H z 为分支 日中的Y i 一2 路所以z z 茌E ( G ) ( 1 i f ) 若z z E ( G ) ( 1 i I R ( z ) ! 由上述
10、证明可知I N c ( N R ( z t ) ) l 芝2 在( ( 2 ) ) 中取z e Z l ，使f ( R ( z ，) ) = ，则Z 2 聋 百，z t 且z t # 聋 E ( G ) ( 否则易得C 的扩圈) 由论断2 ( 2 ) ， c 。：( 名产) n ( 才) = 2 嚷c ；。( z ) nN o ( g ) 又 寻c 砘( z ) n 吆c ：，( z 产) = 泔 ， 才隹c 砘( 才) u 嚷c ：。( 名 ) u ( 才) 所以 I c ：。( z t ) l + l 峰( z ) I + I N o ( # ) I I C l ( 4 ) 由Z 2 的取
11、法可得( z t ) n ( 才) = ，所以I N n ( z 。) I + l ( 砉) l I n l 再注 意到( 3 ) ，( 4 ) 及 I 呀c ：( z t ) l = I N , t c = 。( z t ) l ，I 峰铂( z t ) l = I N # c ：。( z t ) l ， 得下述矛盾 d ( z - ) + d ( 才) = ( I ( z 产) I + I N R ( z t ) 1 ) + ( I ( 磅) I + I N R ( 才) 1 ) 0 情形2 2 m 为奇数 m - - 1 此时有 i = 2 N R ( 仇) l 堡尹h + 1 2 (
12、m 一1 ) 】+ 2 = 一m 2 + 半m 一丁3 g l , 一；又 ，n 一1 m 一1 0 = I ( 忱) f 一I k ( 忱) i = 2= 2 一m 2 + 字m 一挚一；一( 几一m 一1 ) = 一m 2 + 堡乒m a n 2 + a 0 ， 综上，论断4 得证 论断5 ：若存在z R ，使得P ( z ) = 饥，吻) 且 协，) “ 1 ，) ，则有 V _ ( 时) I + l P ( 哆) I m 一2 , N e C v f ) l + I - ( 丐) Ism 一2 证明：不失一般性可假设1 i J m ，则u ，时均存在，取可P ( u 产) 若Y T ，
13、I P u i 此时Y + ( 1 矿) ，否则t J xP Y v + P v i z v i - P Y l 矿尸为扩路 若Y T ，2 P u j 此时Y 一隹J v ( 哼) ，否则v l P v i ：T , V Z f i v i 。P y 一“ 0 + P l m 为扩路 若Y 才P 此时，Y + 隹( 哆) ，否则v x P v z v P v + 1 V - P v f y + P 为扩路 3 2 山东师范大学硕士学位论文 显然，I r P ( 时) I + I N P ( v 2 - ) l ，n 一2 ；同理可得I P ( c ，f ) l + I P ( 1 f ) I
14、s m 一2 记5 1 = u ：口坼( ，) ) ，选取眯m a 朋xI N 兄( v i ) l 中的顶点，从 Ir g Y 书f , N 。之 差最小的顶点Y b 情形1 b 情形1 1 o = 1 由论断4 可知b m ，所以咭，u 产均存在由论断5 可知 ( 呓) I + l P ( 时) I m 一2 ，从而可得 矛盾 d ( u j ) + d ( 讨) - I P ( u 毒) I + I P ( 时) I + l ( 咭) | + I ( 时) I N p ( v 2 ) l + I P ( u ；- ) I + l ( ) I + 1 人r R ( 咭) m 一2 + 7
15、1 , 一m = 几一2 b Sm 一2 + n m = 7 1 , 一2 佗+ 1 ， 情形2 1 ，口= 肌由论断4 可知b 1 ，所以T i ，t i 均存在由论断5 可知 坼( t ) I + I N p ( 1 ，f ) I m 一2 ，从而可得 d ( v 2 ) + d ( 町) = l P ( 呕) I + I N e ( 叮) I + 1 ( 1 ) I + I R ( t i ) I P ( 呕) I + I u p ( 町) I + l ( ) I + I ( 町) m 一2 + 佗一m = 礼一2 n + 1 山东师范大学硕士学位论文 矛盾 情形2 2 a m 显然咭，t 7 手均存在由论断5 可知J P ( 时) I + ；A r P ( 磁) I m 一2 ，从而可得 d ( 时) + d ( 时) = I P ( 咭) + I P ( 时) I + f ( u j ) I + i ( u 产) I l P ( 畦) l + 1 人
