IDENTIFYING CODES IN REGULAR GRAPHS
Florent Foucaud · 2010
An identifying code of a graph G is a dominating set such that the neighbourhood of each vertex within the code is unique. More formally, C is an identifying code if for any pair x, y of vertices of G, N [x] ∩ C 6= ∅ and N [x] ∩ C 6= N [y] ∩ C. They were introduced in [1] and are a variation of other concepts such as metric bases or locating-dominating sets [3]. Given a graph G, let γ(G) denote the identifying code number of G, that is, the size of a minimum identifying code of G. In this talk, we show that the bound γ(G) ≤ n − n 84d holds for any identifiable d-regular graph G for large enough d. This bound is tight (up to a constant) and asymptotically settles a conjecture of the first author, R. Klasing, A. Kosowski and A. Raspaud [2] for the case of regular graphs. The bound is proved using Lovasz’ Local Lemma. We also present sharp bounds for the identifying code number of random d-regular graphs, which is proved to be close to log d d n with high probability.