图的路圈性质及连通性的研究

发布时间：2017-11-22 02:13

  本文关键词：图的路圈性质及连通性的研究

  更多相关文章： Homilton Dominating 路 圈 [s t]-图 2-因子

【摘要】：图论是现代数学的重要分支之一,图的路、圈问题又是图论中一个十分重要而且活跃的研究课题,大量的实际问题可以归结为路和圈的问题.事实上,图论中三大著名难题之一的Hamilton问题本质上也是图的路和圈问题.这方面的研究成果和进展可参见文献[29]-[33].由于直接研究一般图的Hamilton问题往往比较困难,于是人们转而研究不含有某些禁用子图的图类,如无爪图.继Beineke1970年发表的关于线图性质的文章[11]-[12]之后,人们开始关注包含着线图的无爪图.70年代末80年代初,是研究无爪图的一个非常活跃的时期.关于无爪图方面的部分优秀成果可参考[13]-[28].如果图G中任意s个顶点之间至少存在t条边,则称G是[s,t]-图.这一概念是刘春房,王江鲁2005年在[2]中给出的.由于”α(G)≤k当且仅当G是[k+1,1]-图(这里a(G)是图G的点独立数)”[3],所以从某种意义上讲[s,t]-图是图的独立数概念的推广.此外,易举出大量实例,其中所包含的问题可以归结为对[s,t]-图的研究.比如在染色,交通网络,通信系统,计算机的网络配置等方面.目前,对[s,t]-图的研究都集中在其路、圈性质的研究上,已有的研究成果大都是对[s,t]-图中s,t是一些较小的正整数的研究.第一个具有一般意义的研究成果是王江鲁,牟磊在[3]中给出的下边的两个结果：(1)若图G是k-连通[k+2,2]-图,则G或者含有Hamilton圈或者同构于Petersen图或者同构于Kk+2∨Gk.(这里Gk是含有k个顶点的任意图,下同)(2)若图G是k-连通[k+3,2]-图(k≥2),则G或者含有Hamilton路或者同构于Kk+2∨Gk.由这两个结果可以分别推得Chvatal-Erdos和Bondy用点独立数α(G)和连通度k(G)给出的下述经典结果：(a) (Chvatal-Erdos and Bondy[6])设图G的阶n≥3,如果α(G)≤κ(G),则G含有Hamilton圈.(b)(Bondy [7])设图G的阶n≥3,如果α(G)≤κ(G)+1,则G含有Hamilton路.在[6]中Chvatal-Erdos还给出了另一个经典结果：定理[6]设图G的阶n≥3,如果α(G)≤κ(G)-1,则G是Hamilton连通的.在本文的第二章将给出它的推广：定理若图G是k-连通[k+1,2]图,则G或者是Hamilton连通的或者同构于KK∨Gk.鉴于目前对[s,t]-图的研究还处于初级阶段,本文继续了[s,t]-图路圈性质的研究.在第一章中,主要介绍文章中所涉及的一些概念和术语符号,以及本文的研究背景和已有的一些结果.在第二章中,主要研究了[s,t]-图在不同条件下的Hamilton连通性质,得到下面的结果：定理2.1.1若图G是k-连通[k+1,2]-图(k≥2),则G或者是Hamilton连通的或者同构于Kk∨Gk.推论2.1.1设G是n(≥3)阶,k-连通[k+1,2]-图且|G}≥2k+1,则G是Hamilton连通的.推论2.1.2设G是n(≥3)阶δ≥k+l,k-连通[k+1,2]图,则G为Hamilton连通.推论2.1.3设G是n(≥3)阶,α(G)≤k-1,则G为Hamilton连通.定理2.1.2若图G是δ≥k+1,k-连通[k+2,3]-图(k≥2),则G或者是Hamilton连通的或者同构于Kk+1∨Gk+1推论2.1.4 设G是n(≥3)阶,δ≥k+1,k-连通[k+2,3]图且|G|≥2k+3,则G是Hamilton连通的.推论2.1.5设G是n(≥3)阶,δ≥k+2,k-连通[k+2,3]-图,则G为Hamilton连通.在第三章中,讨论了在|Nc(B)|≥k(|NP(B)|≥k)的条件下[s,t]-图的Hamilton的路圈性质,得到下面的结果：定理3.1.1设图G是[k+3,2]-图(k≥2)且不含Hamilton路,P是G的一条最长路,如果对G-V(P)的任一分支B有|NP(B)|≥k,则G同构于Kk+2∨Gk.推论3.1.1若图G是k-连通[k+3,2]-图,则G或者含有Hamilton路或者同构于瓦Kk+2∨Gk.定理3.1.2设图G是δ≥k+1,[k+4,3]-图(k≥2)且不含Hamilton路,P是G的一条最长路,如果对G-V(P)的任一分支B有|NP(B)|≥k,则G同构于Kk+3∨Gk+1.推论3.1.2若G是δ≥k+1的k-连通[k+4,3]-图,则G有Hamilton路或G同构于Kk+3∨ Gk+1.定理3.1.3设图G是[k+2,2]-图(k≥2)且不含Hamilton圈,C是G的一条最长圈,如果对G-V(C)的任一分支B有|NC(B)|≥k,则G或者同构于Petersen图或者同构于Kk+1∨Gk推论3.1.3若图G是k-连通[k+2,2]-图,则G或者含有Hamilton圈或者同构于Petersen图或者同构于Kk+1∨ Gk.定理3.1.4设图G是[k+1,2]-图(k≥2)且不是Hamilton连通的,P是G的一条最长路,如果对G-V(P)的任一分支B有|NP(B)|≥k,则G同构于Kk∨Gk.定理3.1.5设图G是δ≥k+1,[k+2,3]-图(k≥2)且不是Hamilton连通的,P是G的一条最长路,如果对G-V(P)的任一分支B有|NP(B)|≥k,则G同构于Kk+1∨Gk+1.定理3.2.1设图G是δ(G)≥3,[4,2]-图且不含Hamilton圈,G是G的一条最长圈如果对G-V(C)的任一分支B有|NC(B)|≥1,则G有2-因子.推论3.2.1设图G是连通[4,2]-图,若δ(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)|≥k,则G有2-因子.推论3.2.2[10]设图G是n(n≥5)阶k-连通[k+2,1]-图,则G有2-因子.在第四章中,涉及的是[s,t]-图的Dominating性质,得到下面的结果：定理4.1.1若图G是k-连通[k+3,3]-图(k≥2),则G含有Dominating圈.定理4.2.1若图G是k二连通[k+4,3]-图(k≥2),则G含有Dominating路
【学位授予单位】：山东师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5

【参考文献】

中国硕士学位论文全文数据库 前1条

1 程建民;图中强路圈性质的若干充分条件[D];山东师范大学;2009年

，

本文编号：1213104