کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420147 | 683897 | 2012 | 15 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: On the size of identifying codes in triangle-free graphs On the size of identifying codes in triangle-free graphs](/preview/png/420147.png)
In an undirected graph GG, a subset C⊆V(G)C⊆V(G) such that CC is a dominating set of GG, and each vertex in V(G)V(G) is dominated by a distinct subset of vertices from CC, is called an identifying code of GG. The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. For a given identifiable graph GG, let γID(G) be the minimum cardinality of an identifying code in GG. In this paper, we show that for any connected identifiable triangle-free graph GG on nn vertices having maximum degree Δ≥3Δ≥3, γID(G)≤n−nΔ+o(Δ). This bound is asymptotically tight up to constants due to various classes of graphs including (Δ−1)(Δ−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 cc such that the bound γID(G)≤n−nΔ+c holds for any nontrivial connected identifiable graph GG.
Journal: Discrete Applied Mathematics - Volume 160, Issues 10–11, July 2012, Pages 1532–1546