On the ensemble of optimal identifying codes in a twin-free graph

Let G = (V, E) be a graph. For v ∈ V and r ≥ 1, we denote by B_G,r(v) the ball of radius r and centre v. A set (Formula presented.) is said to be an r-identifying code if the sets (Formula presented.) , v ∈ V, are all nonempty and distinct. A graph G which admits an r-identifying code is called r-twin-free, and in this case the smallest size of an r-identifying code is denoted by γ_r(G). We study the ensemble of all the different optimalr-identifying codes C, i.e., such that |C| = γ_r(G). We show that, given any collection (Formula presented.) of k-subsets of V₁={1,2,…,n}, there is a positive integer m, a graph G = (V, E) with (Formula presented.) , where V₂ = {n + 1 ,…, n + m}, and a set (Formula presented.) such that (Formula presented.) is an optimal r-identifying code in G if, and only if, (Formula presented.) for some (Formula presented.). This result gives a direct connection with induced subgraphs of Johnson graphs, which are graphs with vertex set a collection of k-subsets of V₁, with edges between any two vertices sharing k−1 elements.