关于近似二部图边覆盖染色的一个充分条件

来源 :山东大学学报：理学版 | 被引量 : 0次 | 上传用户：kathrynde

【摘要】

：

设G是一个简单图，其顶点集为V（G）而边集为E（G）．S包含E（G）称为G的一个边覆盖，如果由S导出的子图是G的一个生成子图．G的边覆盖色数X’c（G）是E（G）所能划分成的最大边覆盖数．已知δ-1≤X’c（G）≤δ

【作者】

：

王纪辉

【机构】

：

山东大学数学与系统科学学院,济南大学理学院

【出处】

：

山东大学学报：理学版

【发表日期】

：

2006年1期

【关键词】

：

近似二部图边覆盖染色最小度顶点边覆盖色数 nearly bipartite graph edge covering coloring minimum de

【基金项目】

：

国家自然科学基金资助项目（10471078）,山东省自然科学基金资助项目（Y2003A01）

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

设G是一个简单图，其顶点集为V（G）而边集为E（G）．S包含E（G）称为G的一个边覆盖，如果由S导出的子图是G的一个生成子图．G的边覆盖色数X’c（G）是E（G）所能划分成的最大边覆盖数．已知δ-1≤X’c（G）≤δ，由此将X＇c（G）=δ的图称为CⅠ类图，否则称为CⅡ类图．显然，图的边覆盖染色分类问题是NP-完全的．给出了近似二部图是CⅠ类图的一个充分条件，而且该条件中的下界是最好的．

其他文献

青海省融入“一带一路”倡议的SWOT分析

＂一带一路＂是我国近年来提出的新的经济发展战略,为我国经济发展带来了新的机遇和挑战,也为我国同其他各国之间的合作带来了契机。青海作为我国西部大省,作为＂一带一路＂沿途的重

期刊

“一带一路”青海省SWOT分析发展对策

关于马克思主义社会建设理论研究的深入思考

马克思主义社会建设,是随着社会形态的发展,随着国家体制的完善与进步,逐步摆在我们面前的问题。马克思恩格斯所处的时代及当时社会的特殊形态要求他们更多地关注的是革命道

期刊

马克思主义社会建设理论研究

对硝基苯酚在镁铝型双金属氢氧化物及其煅烧产物上的吸附

对合成的Mg2Al型层状双金属氢氧化物（LDH）及其煅烧产物（CLDH）进行了表征．研究了对硝基苯酚在LDH和CLDH上的吸附．结果表明，对硝基苯酚在LDH和CLDH上均可发生吸附，其吸附等温线均符合Fr

期刊

层状双金属氢氧化物对硝基苯酚吸附结构重建layered double hydroxide p- nitrophenol adsorption str

浅谈唢呐和笙的关系

中国民族乐器种类繁多，乐曲更是数不胜数，在这个民族乐器大家族中，唢呐和笙是很重要的两件民族乐器，他们之间的关系是密不可分的，配合起来真可谓珠联璧合，如鱼得水。今天就唢呐和笙

期刊

唢呐中国民族乐器笙乐曲

农业经济管理的现状与发展趋势分析

当前,我国诸多地区都主打开放型农业发展模式,它不但能满足地方农业发展需求,也能够提高农业经济管理水平,为地方农业经济创收.本文以江西省为例,简要探析了该省在当前实施开

期刊

农业经济管理现状开放型思路发展趋势江西省

L-拓扑空间中的＊-拟仿紧性

利用α-正则闭远域族在L-拓扑空间中定义了一种新的仿紧性，即＊-拟仿紧性，并用半内部对其进行了刻划。研究了＊-拟仿紧性所具有的一些性质，比如L-good extension，正则闭遗传，弱同胚不

期刊

L-拓扑空间α-正则闭远域＊-拟仿紧性诱导空间L-topological space a-regular closed remote family ＊-

谈谈当下江苏群众美术创作展赛活动

我省群众美术展览创作展赛活动的现状：其一,继承有余,创新不够;其二,精品匮乏,心态浮躁;其三,素质不高,队伍老化。这些情况必须改变。以下提出个人见解仅供参考。

期刊

群众美术创作展赛活动

冠洋集团董事长刘镇纲与各国总统政要交谈探讨一带一路文化合作

近日,亚洲音乐盛典暨对话总统论坛在中国深圳"世界之窗"荣耀盛启。本次活动以"音乐盛典,文化产业"为主题,冠洋集团董事刘镇纲与爱尔兰前总理伯蒂·埃亨,意大利前总理罗马

期刊

世界之窗历史意蕴文化产业一带一路罗马诺刘镇交流互鉴斯托扬诺夫

俄罗斯勘察加地区设立格洛纳斯测量站

2017年6月，来自时间协测和导航支持科学研究院信息分析中心的专家在勘察加地区设立了全球卫星导航系统测量收集站。该项工作是与国家科学预算支持的“俄罗斯科学院统一地球物

期刊

俄罗斯科学院勘察测量全球卫星导航系统科学研究院信息分析地球物理科学预算

含时线性Klein-Gordon方程的解

把K-G方程通过变量代换化简成对时间一阶求导的形式，即薛定谔方程的形式。然后运用不变量方法求解含时线性情况下K-G方程的解，并讨论2种相关的情况：相对论非含时和非相对论含时

期刊

K-G方程不变量方法含时K-G方程的解K-G equation Lewis-Riesenfeld invariant method the solutio

关于近似二部图边覆盖染色的一个充分条件

其他学术论文