强-[s,t]图的路圈性质及拟无爪图在H-局部连通条件下的1-2可扩性

来源 :山东师范大学 | 被引量 : 0次 | 上传用户:zhk42
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的路和圈问题是图论中十分重要而且活跃的研究课题,由于路和圈是分析和刻画图的常用工具,有大量的实际问题可以归结为图的路和圈问题(例如我们经常见到的一笔画游戏).图论中三大著名难题之一的Hamilton问题本质上也是图的路和圈问题.关于路和圈的研究,国内外许多学者做了大量的研究工作并且取得了不少的研究成果.可参见文献.经过几十年的发展,图的路圈性质所涉及的内容日益丰富和具体.路的方面包括图的HamUton路(可迹性),齐次可迹性,最长路,Hamilton连通,路可扩,泛连通等等.圈的方面包括图的Hamilton圈,(点)泛圈,完全圈可扩,最长圈,点不交的圈,圈覆盖等等.  由于直接研究一般图的HamUton问题比较困难,于是人们转而研究一些特殊图的Hamilton问题.比如利用禁用子图给出图类,其中有代表性的是无爪图.研究无爪图的最初动机来源于1968,1970年的Beineke发表的关于线图性质的两篇文章.可参见文献.自此之后,人们开始关注包含着线图的无爪图.70年代末80年代初对无爪图的研究成为图论中的著名课题.关于无爪图方面的部分优秀成果可参见文献.此外无爪图的概念也被从不同的角度推广到了更大的图类,如半无爪图,几乎无爪图,爪心独立图,(Khp,q)-图,DCT图等等.由于无爪图中的很多很好的结果推广到几乎无爪图的难度非常大.所以滕延燕,尤海燕2003年在此基础上提出拟无爪图的概念.它包含无爪图类但却包含在几乎无爪图类中.这里我们可以将半无爪图,几乎无爪图,拟无爪图统称为类无爪图.近年来,其他一些新型的禁用子图也不断的被提出.  2005年,刘春房在中定义了一种新的图类M-图,即任意s个点之间至少含有t条边.程建民在[s,t]-图的基础上提出了强-[s,t]图的概念,即任意s个点之间至少含有t条独立边.[s,t]-图的特点是其边的分布相对比较均匀.[s,t]-图的概念可视为图的点独立数概念的推广,如在交通网络,通信网络,计算机的网络配置等方面的实际问题可归结为对[s,t]-图的研究.对[s,t]-图和强-[s,t]图的研究目前处于初级阶段,并且所有的研究都集中在对其路圈性质的研究上.相关研究成果可参见文献.  连通和局部连通是探究图的路圈性质的常用条件.在局部连通的定义提出后,张存全在1989年提出了半局部连通的定义,研究了无爪图在半局部连通条件下的一些性质.滕延燕和尤海燕在2002年定义了几乎局部连通图.而赖宏建在2004年提出了三角连通的概念,证明了无爪图在三角连通下的一些结果.2008年,刘明颖提出了H-局部连通的概念,初步讨论了在H-局部连通条件下无爪图和半无爪图的路圈性质.  本文主要研究了强-[s,t]图的路和圈的性质及拟无爪图在H-局部连通条件下的路圈性质.  在第一章中主要介绍文章中所涉及的一些概念和术语符号,以及本文的研究背景和已有的一些结果.  在第二章中主要研究了强-[s,t]图在不同条件下的路圈性质,得到下面的结果:  定理2.1.1设G是强-[k+3,2]图且不含Hamilton圈,C是G的一个最长圈,如果对G-V(C)的任一分支H有|Nc(H)|>k,则G同构于(k+1)K2VGk(Gk为含有k个点的任意图).  推论2.1.1设G是 k-连通强-[k+3,2]图,8(G)> k+1,则G含有Hamilton圈或者同构于(k+1)K2VGk.  定理2.2.1设G是强-[k+4,2]图且不含Hamilton路,P是G的一个最长路,如果对G-V(P)的任一分支H有|Np(H)|> k,则G同构于(k+2)K2VGk(G k为含有k个点的任意图).  推论2.2.1设G是k-连通强-[k+4,2]图,且6(G)> k+1,则 G含有Hamilton路或者同构于(k+2)K2 V Gk.  定理2.3.1设G是k-连通强-[k+2,3]图,且6(G)>(k+1),则 G是Hamilton连通的或者同构于kK2VGk.(Gk为含有k;个点的任意图).  推论2.3.1设G是k-连通强-[k+2,2]图,且6(G)> k+1,则 G是Hamilton连通的或者同构于kK]VGk.(Gk为含有k;个点的任意图)  在第三章中,讨论了2-连通,局部连通强-[5,2]图的路可扩性,得到了下面的结果:  定理3.1.1若G是2-连通,局部连通强-[5,2]图,则G是路可扩的.  在第四章中研究了在P3-局部连通的条件下拟无爪图的1-2可扩性,得到下面的结果:  定理4.1设G是连通,Pa-局部连通的拟无爪图,则G是1-2可扩.  推论4.1设G是连通,Pa-局部连通的无爪图,则G是1-2可扩.
其他文献
In this paper,we study lag synchronization between two coupled networks and apply two types of control schemes,including the open-plus-closed-loop(OPCL) and ada
课堂是一个充满活力的生命整体,处处蕴涵着矛盾,其中预设与生成之间的平衡与突破就是一个永恒的主题。下面我就结合《勇于承担责任》这一教学案例,谈谈如何处理好初中思想品
分类问题中的不均衡问题目前是一个被国内外学者关注的(相对地)新问题。本文主要以分类不均衡问题和类不均衡问题的算法为主要研究内容,试图分别从数据预处理和模式选择这两个
本文研究了具有三次项的 Van der Pol-Duffing非线性时滞系统的Hopf分支和稳定性,并分析了当系统在经历Hopf分支时,小周期扰动对系统的影响,通过构造中心流形和积分平均法,讨论了
本文主要研究具脉动的一阶脉冲时滞微分系统(此处公式省略)的稳定性,其中系统(I)与(II)的解轨线与每个脉冲面可至多碰撞有限次.  脉冲微分系统是上世纪八十年代初开始兴起的一
我国于2014年1月1日起全面执行《行政事业单位内部控制规范(试行)》。标志着我国内部控制建设开始了一个新的阶段,内部控制建设的范围由原来单一的企业内部控制扩大为包含行
Feijiu网2016-05-10报道:美国林业及纸业协会(AF&PA)近日公布的统计数据显示,2015年美国以再生利用为目的的废纸回收率达66.8%。该协会负责人表示,美国废纸回收率的持续提高,
近年来,随着大规模集合电路,微电子技术,大规模互联网络的飞速发展,人们对网络的拓扑结构要求越来越高.图的理论及其在各个领域的广泛应用越来越受到数学界和其他科学界的重视.网
Non-:Fickian扩散问题刻画了诸如流体在高聚物中的渗透和扩散,湿气在高聚物膜中的迀移等重要物理现象,在实际工业生产中具有大量的应用.大量的实验表明,流体在上述渗透与扩散过程
摘要:水利工程概、预算的编制是一项十分严肃而细致的工作,是设计文件的重要组成部分,是决定工程结构设计的综合文件,是基本建设管理工作中的依据。本文分析了水利工程概预算的分类及重要性,并针对水利工程概预算需注意的问题进行了阐述。  关键词:水利工程;概预算;分类;重要性;问题  Abstract : The preparation of hydraulic engineering project, t
期刊