On the size of identifying codes in triangle-free graphs

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.