论文部分内容阅读
图论是现代数学的重要分支之一，图的路、圈问题又是图论中一个十分重要而且活跃的研究课题，大量的实际问题可以归结为路和圈的问题.事实上，图论中三大著名难题之一的Hamilton问题本质上也是图的路和圈问题.这方面的研究成果和进展可参见文献.由于直接研究一般图的Hamilton问题往往比较困难，于是人们转而研究不含有某些禁用子图的图类，如无爪图.继Beineke1970年发表的关于线图性质的文章之后，人们开始关注包含着线图的无爪图.70年代末80年代初，是研究无爪图的一个非常活跃的时期.关于无爪图方面的部分优秀成果可参考. 如果图G中任意s个顶点之间至少存在t条边，则称 G是[s,t]-图.这一概念是刘春房，王江鲁2005年在中给出的.由于”a(G)2),则G或者含有Hamilton路或者同构于Kk+2VGk. 由这两个结果可以分别推得Chvatal-Erdis和Bondy用点独立数a(G)和连通度k:(G)给出的下述经典结果： (a)(Chvatal-Erdos and Bondy)设图G的阶n>3,如果a(G)3,如果a(G)3,如果a(G)2)，则 G或者是HamHton连通的或者同构于KkVGk. 推论2.1.1设G是n(>3)阶,k-连通[k+1,2]—图且|G|>2 k+1，则G是Hamilton连通的. 推论2.1.2设G是n(>3)阶,k+1，k-连通[k;+1,2]图，则G为Hamilton连通. 推论2.1.3设 G是n(23)阶,a(G)< k—1，则 G为H a m说on连通. 定理2.1.2若图G是6> k+1，k—连通[k+2,3]—图(fc>2)，则 G或者是Hampton连通的或者同构于Kk+1VGk+i. 推论2.1.4设 G是n(23)阶,6> k+1，k—连通[k+2,3]图且|G|>2k+3，则 G是Hampton连通的. 推论2.1.5设G是n(>3)阶,6>&+2，连通[k+2,3]—图，则G为Ham沿on连通. 在第三章中，讨论了在|NC(B)|> k(|Np(B)|>幻的条件下[s,t]—图的Hampton的路圈性质，得到下面的结果： 定理3.1.1设图G是[k+3,2]—图(k>2)且不含Hamilton路,P是 G的一条最长路,如果对G-V(P)的任一分支B有|Np(B)|则G同构于VGk. 推论3.1.1若图G是;fc-连通[k+3,2]-图，则 G或者含有Ham说on路或者同构于Kk+2VGk. 定理3.1.2设图G是6>k+1,[k+4,3]-图>2且不含Hamilton路,P是G的一条最长路，如果对G-V(P)的任一分支B有|Np(B)|>k,则 G同构于Kk+3VGk+1. 推论3.1.2间若 G是6>k+1的k-连通[k+4,3]—图，则G有Ham沿on路或G同构于Kk+3VGk+i. 定理3.1.3设图G是[k+2,2]—图(k>2)且不含Hamilton圈,C是G的一条最长圈，如果对G—V(C)的任一分支B有|NC(B)|>&,则G或者同构于Petersen图或者同构于Kk+1VGk. 推论3.1.3间若图G是I连通[&+2,2]-图，则 G或者含有Ham沿on圈或者同构于Petersen图或者同构于Kk+iVGk. 定理3.1.4设图G是[k+1,2]—图(k>2)且不是Hamilton连通的，P是G的一条最长路，如果对G—V(P)的任一分支B有|Np(B)|则G同构于KkVGk. 定理3.1.5设图 G是6>k+1,[k+2,3]—图(k>2)且不是Hamilton连通的,P是G的一条最长路,如果对G—V(P)的任一分支B有|Np(B)|则G同构于Kk+iVGk+i. 定理3.2.1设图G是6(G)>3,[4,2]—图且不含Hamilton圈,C是G的一条最长圈如果对G—V(C)的任一分支B有|NC(B)|>1,则 G有2-因子. 推论3.2.1[叫设图G是连通[4,2]—图，若6(G)>3,则 G有2-因子. 定理3.2.2设图G的阶为n(n>5),是[k+2,1]—图(k>2)且不含Hamilton圈,C是G的一条最长圈如果对G—V(C)的任一分支B有|NC（B)|则G有2-因子. 推论3.2.2[叫设图G是n(n>5)阶k-连通[k+2,1]—图，则G有2-因子. 在第四章中，涉及的是[s,t]-图的Dominating性质，得到下面的结果： 定理4.1.1若图G是k—连通[&+3,3]-图(&>2)，则G含有Dominating圈. 定理4.2.1若图G是k—连通[k+4,3]-图(k>2)，则G含有Dominating路.