【摘 要】
：
图的坚韧度是图的重要参数之一,自Chvatal在1973年提出的这个概念后,关于图坚韧度的性质就有了很多的结果,但是仍然有许多有名的猜想和公开问题至今未获解决,其中之一就是：对
论文部分内容阅读
图的坚韧度是图的重要参数之一,自Chvatal在1973年提出的这个概念后,关于图坚韧度的性质就有了很多的结果,但是仍然有许多有名的猜想和公开问题至今未获解决,其中之一就是：对于任意的图G,是否存在一个有限的常数t0满足每一个t0-坚韧的图G都含有一个哈密尔顿圈.图的坚韧度与哈密尔顿性之间的关系是研究的热点问题之一.在研究图的哈密尔顿性时,通常要用一些性质或参数来找出图具有哈密尔顿性的条件,本文研究的就是图的坚韧度与哈密尔顿性之间的关系,即利用图的坚韧度参数来对两种特殊图类的哈密尔顿性进行了刻画.一个非完全图G的坚韧度是指最小的t满足：存在一个点割集S使得G删除它会产生(|S|)、t个连通分支.计算一个一般图的坚韧度是一个NP-困难问题.对于k≥2,一个图G叫故k-分裂图,如果它的点集可以划分为一个集合I和一个集合C使得导出子图G[I]是一个独立集,G[C]是一个完全k-部图.特别的,如果令G[C]是一个完全图时我们称之为分裂图.Woeginger证明了一个分裂图的坚韧度是可以在多项式时间内计算出来的.对于任意的整数p≥3,Cp*-图是指它由p个非空互不相交的独立集A1,A2…,Ap构戎且集合Ai和Ai+1(i=1,2….p-1)做为其导出子图是一个完全二部图,同时集合Ap和A1做为导出子图也是一个完全二部图.Broersma等人证明了C5*-图是哈密尔顿的充分必要条件为它是1-坚韧的.本篇文章前部分首先类似于分类图证明了k-分裂图的坚韧度是可以在多项式时间内计算出来的,其次证明了顶点数大于等于3的k-坚韧的k-分裂图是哈密尔顿的(k>2).最后我们推广了Broersma等人的结果,证明了对于任意的整数p≥3,Cp*-图是哈密尔顿的充分必要条件为它是1-坚韧的.
其他文献
Hardy空间的实变理论是调和分析研究的核心内容之一,在分析学领域和偏微分方程中都有重要的应用.设A是Rn上的一个扩张矩阵,φ:Rn×[0,∞)→[0,∞)是一个Musielak-Orlicz函数.
设G=(V,E)是一个简单图,C是G的一个至少有两个顶点的子图,如果C是一个极大的完全子图,则称C是图G的一个团.设D是图G的一个顶点子集,如果对于G的任意一个团C,D∩C?=?,则称D是
传染病动力学模型的理论研究,给我们预防和控制各类疾病提供了理论上的依据.本文通过运用传染病动力学、微分方程定性及稳定性理论,主要采用嵌套反证的方法,研究了三类连续的
广义线性模型是经典线性模型的扩展,其因变量不再限制在正态分布,而是扩展到指数分布族,通过连接函数将自变量和因变量之间的关系设定为非线性关系,这不仅为拟合属性变量和取
生态用地不仅为动植物提供了庇护场所,也为人类提供了各项生态服务,一直以来都扮演着极为重要的角色。人口数量的激增使得人类活动区域不断扩张,大量生态用地不断被取代。随着环境保护理念的普及和可持续发展战略的实施,人民逐渐意识到生态用地的价值。对生态用地的现状和变化进行归纳,分析影响生态用地变化的驱动因子,模拟生态用地的变化方向,对生态保护政策的制定及土地资源的合理利用有重大意义。本文依托中科院资源环境科
调和分析主要研究的对象是函数空间和一些算子.Marcinkiewicz积分算子作为调和分析中的经典算子之一.近些年来,对于Marcinkiewicz积分算子、参数型M arcinkiewicz积分算子及
Indian hedgehog(Ihh)蛋白是Hedgehog分泌蛋白家族中重要的一员,对胚胎期和出生后的软骨形成和发育起着重要的调控作用。在自然条件下,翻译后的Ihh蛋白前体(46k D)会发生分子
传染病的防制是关系到人类健康的国计民生的重大问题,对疾病流行规律的定量研究是防制工作的重要依据,长期以来,人类与各种传染病进行了不屈不挠的斗争,使得天花被消灭,麻风
鸡蛋是重要的动物蛋白质来源,深受广大消费者喜爱。目前,洁蛋已成为供应城市的主要商品蛋形式,与传统的土鸡蛋相比,洁蛋更易腐败变质,影响产品流通。本试验研究了不同涂膜包
在很多应用中条件高分位数的估计都是非常重要的。分位数回归提供了一个非常自然和有效的方法去估计协变量在响应分布的不同尾处的影响。然而传统的分位数回归在响应分布的高