• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Offensive r-alliances in graphs
【24h】

Offensive r-alliances in graphs

机译：图形中的冒犯性联盟

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Let G = (V, E) be a simple graph. For a nonempty set X subset of V, and a vertex v is an element of V, delta(X) (v) denotes the number of neighbors v has in X.Anonemptyset S subset of V is an offensive r-alliance in G if delta(S)(v) >= delta(S)- (v) + r, for all v is an element of partial derivative(S), where partial derivative(S) denotes the boundary of S. An offensive r-alliance S is called global if it forms a dominating set. The global offensive r-alliance number of G, denoted by Y-r(0)(G), is the minimum cardinality of a global offensive r-alliance in G. We show that the problem of finding optimal (global) offensive r-alliances is NP-complete and we obtain several tight bounds on Y-r(0)(G). (c) 2008 Elsevier B.V. All rights reserved.
机译：令G =（V，E）为简单图形。对于V的非空集X子集，并且顶点v是V的元素，delta（X）（v）表示v在X中具有的邻居数.V的非空集S子集是G中的进攻性r-联盟delta（S）（v）> = delta（S）-（v）+ r，因为所有v都是偏导数（S）的元素，其中偏导数（S）表示S的边界。令人讨厌的r-联盟如果S形成主导集，则称为S。 G的全局进攻性r-联盟数由Yr（0）（G）表示，是G中全局进攻性r-联盟的最小基数。我们证明了寻找最优（全局）进攻性r-联盟的问题是NP完全，我们在Yr（0）（G）上获得了几个紧边界。 （c）2008 Elsevier B.V.保留所有权利。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号