论文部分内容阅读
路和圈的问题一直是图论中的热点研究领域.路和圈是图的两种基本结构,是分析刻画图的有力工具.有关这方面的研究成果和进展可参见文献[34]-[38]事实上,图论中的三大著名难题之一的Hamiltom问题本质上也是图的路和圈问题.经过几十年的发展,路圈性质所涉及的内容也日益丰富.路的方面包括可迹性,最长路,Hamilton连通,泛连通,路可扩等等；圈的方面包括Hamiltom圈,Dominating圈,最长圈,点泛圈,完全圈可扩,圈覆盖等等.由于直接研究一般图的Hamilon问题往往比较困难,于是人们转而研究不含某些禁用子图的图类.继Beinekel968.1970年发表的关于线图性质的两篇文章[17]-[18]之后,人们开始关注包含线图的五爪图.70年代末80年代初是研究无爪图的一个非常活跃的时期.关于无爪图的部分优秀成果可参见[2]-[4],[19]-[34].无爪图的概念也被推广到了更大的图类,如半无爪图,几乎无爪图等等.其中半无爪图的某些研究进展可参见[35]-[37].本文主要对子图的度条件（任意两个不相邻子图的度和）与路圈性质（包括可迹性,Hamilron圈,Hamilon连通等）之间的关系进行了一些探索,得出了无爪图及半无爪图的路圈性质的几个充分条件.在第一章中,我们主要介绍文章中所涉及的一些概念和术语符号,以及本文的研究背景和已有的一些结果.在第二章中,我们主要研究了无爪图在不同子图的度条件下的路圈性质,得到下面的结果：定理2.1.3设图G是n阶连通无爪图,如果G中任意同构于K1,P3的不相邻导出子图H1,H2的度之和d（H1）+（H2）≥n-2,则G是可迹的.定理2.2.6设G是n阶2-连通无爪图,如果G中任意两个同构于K2（2阶完全图）的不相邻子图H1,H2满足D（H1）+（H2）≥n-2,则G有Hamilton圈.推论2.2.7设图G是n阶2-连通无爪图,如果δ（G:K2）≥n/2-1,则G有Harmilton圈.定理2.3.3设G是n阶3-连通无爪图,如果G中任意两个同构于K2（2阶完全图）的不相邻子图H1,H2满足d（H1）+d（H2）≥n;则G是Hamilton连通的.推论2.3.4设G是n阶3-连通无爪图,如果G中任意两个同构于K2（2阶完全图）的不相邻子图H1,H2满足δ（G:K2）≥n/2,则G是Hanilton连通的.定理2.4设G是n阶4-连通无爪图,如果G中任意同构于K3和同构于K2的不相邻子图H1,H2的度之和d（H1）+d（H2）≥n,则G中任意两点之间都存在控制路.在第三章中,我们讨论了半无爪图在子图的度条件下的可迹性,得到下面的结果：定理3.4设G是n阶2-连通半无爪图,如果G中任意两个同构于K2（2阶完全图）的不相邻子图H1,H2满足d（H1）+d（H2）≥n-1,则G是可迹的.推论3.5设G是n阶2-连通半无爪图,如果G中任意两个同构于K2（2阶完全图）的不相邻子图H1,H2满足δ（G:K2）≥n-1/2,则G是可迹的.