...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >On the size of identifying codes in triangle-free graphs
【24h】

On the size of identifying codes in triangle-free graphs

机译：关于无三角形图中识别码的大小

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

摘要

In an undirected graph G, a subset C?V(G) such that C is a dominating set of G, and each vertex in V(G) is dominated by a distinct subset of vertices from C, is called an identifying code of G. The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. For a given identifiable graph G, let ~(γID)(G) be the minimum cardinality of an identifying code in G. In this paper, we show that for any connected identifiable triangle-free graph G on n vertices having maximum degree Δ<3, ~(γID)(G)≤n-nΔ+o(Δ). This bound is asymptotically tight up to constants due to various classes of graphs including (Δ-1)-ary trees, which are known to have their minimum identifying code of size n-nΔ-1+o(1). We also provide improved bounds for restricted subfamilies of triangle-free graphs, and conjecture that there exists some constant c such that the bound ~(γID)(G)≤n-nΔ+c holds for any nontrivial connected identifiable graph G.
机译：在无向图G中，一个子集C？V（G）使得C是G的主导集，并且V（G）中的每个顶点都由来自C的不同顶点子集所主导，称为G的识别码识别码的概念由Karpovsky，Chakrabarty和Levitin于1998年引入。对于给定的可识别图G，令〜（γID）（G）为G中识别码的最小基数。对于最大度数Δ<3的n个顶点上的任何可连接的可识别的无三角图G，〜（γID）（G）≤n-nΔ+ o（Δ）。由于包括（Δ-1）-ary树在内的各种图的类别，该边界渐近地趋近于常数，已知这些图的最小标识码为n-nΔ-1+ o（1）。我们还为无三角形图的受限子族提供了改进的边界，并推测存在某个常数c，使得任何非平凡可连接图G的约束〜（γID）（G）≤n-nΔ+ c都成立。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号