【摘 要】
：
我们用g(s,t)来表示最小的整数使得给定两个非负整数S和t,当图G满足δ(G)≥g(s,t)时,这个图的点集V(G)可以划分为两个部分V1和V2,两个部分的导出子图分别满足δ(G[V1])≥s以
论文部分内容阅读
我们用g(s,t)来表示最小的整数使得给定两个非负整数S和t,当图G满足δ(G)≥g(s,t)时,这个图的点集V(G)可以划分为两个部分V1和V2,两个部分的导出子图分别满足δ(G[V1])≥s以及δ(G[V2])≥ t.Stiebitz已经证明了g(s,t)≤s+t+1,Kaneko和Diwan分别在特殊图类上改进了这个结果,证明出了G满足g(G)≥4时g(s,t)≤s+t (s,t≥1),或者当G满足g(G)≥5时有g(s,t)≤s+t-1 (s,t≥2),其中g(G)是图G的围长.Liu和Xu进一步强化了Kaneko和Diwan的结果,证明了当图G不是K3且无(K4-e)结构时有g(s,t)≤s+t(s,t≥1)和当图G满足在无3-圈的图下没有两个4-圈共边结构时有g(s,t)≤s+f-1(s,t≥2).Bazgan,Tuza和Vanderpooten分别根据Stiebitz,Kaneko和Diwan的证明给出了可以在多项式时间内可以找出这些划分的算法.在本学位论文中,我们根据Liu和Xu的证明给出相应的可以在多项式时间内找出这些划分的算法.
其他文献
粘性丝孢酵母作为一种油脂微生物,能够将碳水化合物与普通的油脂转化为微生物油脂储存在体内,但不能直接利用木质纤维素类的碳源合成微生物油脂。β-葡萄糖苷酶(β-glucosida
量子群的典范基在量子群及其表示理论中起着重要作用,是研究量子群及其表示理论的主要工具.然而,确定量子群的典范基元素不是一件容易的事情,只有少数量子群的典范基元素被精
微囊藻水华的发生日趋严重,很多地方已经延续到了深冬。越冬细胞作为“种子”对来年水华的发生至关重要。入冬以后“温度骤降—进入寒冬”及“温度骤降—回暖—再降温”的冷
随着以Internet为代表的网络信息技术的蓬勃发展,现代社会已经日益网络化,人类也进入了复杂网络时代。然而任何事物都是辨证的,复杂网络也是如此。网络化时代给我们带来了空
本文研究了带位势H的弱F-调和映照,BMO猜想和S. Meata猜想,以及广义Chen猜想等相关问题.首先引入带位势H的弱F-调和映照的定义.利用应力-能量张量方法得到带位势H及外围流形
本文,主要研究两个问题,周期性双组份μρ-Hunter-Saxton系统在某固定范围内分布式精确控制和渐近稳定性.对于周期性双组份μρ-Hunter-Saxton系统的分布式精确控制问题,我们
记Pk/qk,k≥0表示无理数θ的连分数展开式的渐近分数.我们称符号值序列（pk/qk）,t≥0为θ的雅可比序列. Girstmair证明了e的雅可比序列是周期为24的纯周期序列,e2的雅可比序列是
1951年,K. itO创建了Ito型随机微分方程(SDEs)理论,此后SDEs得到快速发展SDEs可以用来描述现实世界中的一些随机现象,广泛应用于信息与控制、工程控制、统计物理学以及生态学
设n,h,q为正整数且q>2,(h,q)=1,χ是模q的一个Dirichlet特征.习惯上称为L-函数的均值,其中L(s,χ)是Dirichlet L-函数.当n=1时,很多人研究了Dirichlet L-函数的均值表达式问
逻辑控制网络是由一系列逻辑状态变量、逻辑控制变量以及逻辑函数所构成的定义在有限集上的离散动态控制系统,它在生物基因调控网络中有重要的实际应用背景.近些年来,逻辑控