含4-圈且不含3-圈的P4-等可覆盖图的刻画

• 作者: 帅天平 王琪瑞
• 来源期刊: 软件
• 学科: 数学
• 关键词: 计算机软件与理论 等可覆盖 图论 覆盖
• 年，卷（期）: 2015,（10）
• 所属期刊栏目: 基金项目论文
• 页码范围: 5-8,12
• 页数: 5页
• 分类号: O157.5
• 字数: 5102字
• 语种: 中文
• DOI: 10.3969/j.issn.1003-6970.2015.10.002

摘要

覆盖问题是图论的主要研究内容,也是理论计算机科学中的重要内容之一,具有重要的理论意义与应用价值,在计算机图形学和运筹学中都有广阔的应用前景.在通信行业,基于覆盖问题的研究基础,可以简化通信网络的层次分布与优化.特殊的覆盖可以导出图的一些良好的性质,鉴于这类问题在实际应用中的价值,此类研究近期应用于图的结构性之上.图论中的覆盖问题有很多种,其中包括等可覆盖问题:如果一个图G的每个极小H-覆盖都是它的最小H-覆盖,则称G为H-等可覆盖的.本文仅考虑H为P4时的情形.经过讨论,本文通过对含4-圈且不合3-圈的图的特征进行刻画,给出了判定任意一个含4-圈且不合3-圈的图是否是P4-等可覆盖的充分必要条件.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	帅天平	北京邮电大学理学院	8	8	2.0	2.0
2	王琪瑞	北京邮电大学理学院	1	3	1.0	1.0