On the size of identifying codes in triangle-free graphs

In an undirected graph G, a subset C subset of 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 gamma(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 Delta >= 3, gamma(ID)(G) <= n - n/Delta+o(Delta). This bound is asymptotically tight up to constants due to various classes of graphs including (Delta - 1)-ary trees, which are known to have their minimum identifying code of size n - n/Delta-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 gamma(ID)(G) <= n - n/Delta + c holds for any nontrivial connected identifiable graph G. (C) 2012 Elsevier B.V. All rights reserved.