Spider图的[1,2]—支配数研究

2018年第10期

【字体:


  【摘要】图g的一个点集s是一个[1,2]-支配集,则有每个不在s中的点满足至少与s中的1个点且至多与s中的2个点相邻.通过分析,证明spider图的支配数性质结论.并讨论一种计算[1,2]-数的近似算法.

  【关键词】spider图;[1,2]-支配数;近似算法

  【基金项目】南京工业大学浦江学院科研项目(njpj-2016-2-02).

  一、引 言

  一个集合sv(g)若被称为圖g的支配集(dominating set)[1],则有任意的顶点v或者在s中或者与s中的点相邻接.我们把顶点数目最少的支配集称为图的最小支 ……阅读全文

刊社简介 | 联系我们 | 广告刊例 | 收藏本站 | 设为首页

主办: 数学学习与研究杂志社 Copyright◎1997-2018

技术支持,电子版全球营销龙源

互联网出版许可证:新出网证(京)字066号

京公海网安备110108001919

电信与信息服务业务经营许可证:京ICP证060024