度约束下顶点划分的算法

发布时间：2019-09-11 12:58

【摘要】：我们用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的证明给出相应的可以在多项式时间内找出这些划分的算法.
【学位授予单位】：南京师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5

【相似文献】