Refereed journal article or data article (A1)
On the ensemble of optimal identifying codes in a twin-free graph
List of Authors: Honkala I, Hudry O, Lobstein A
Publisher: SPRINGER
Publication year: 2016
Journal: Cryptography and Communications
Journal name in source: CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES
Journal acronym: CRYPTOGR COMMUN
Volume number: 8
Issue number: 1
Start page: 139
End page: 153
Number of pages: 15
ISSN: 1936-2447
DOI: http://dx.doi.org/10.1007/s12095-015-0148-3
Abstract
Let G = (V, E) be a graph. For v is an element of V and r >= 1, we denote by B-G,B- r (v) the ball of radius r and centre v. A set C subset of V is said to be an r-identifying code if the sets B-G,B- r (v) boolean AND C, v is an element of 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 gamma(r)(G). We study the ensemble of all the different optimal r-identifying codes C, i.e., such that broken vertical bar C broken vertical bar = gamma(r)(G). We show that, given any collection A of k-subsets of V-1 = {1, 2, . . . , n}, there is a positive integer m, a graph G = (V, E) with V = V-1 boolean OR V-2, where V-2 = {n + 1, . . . , n + m}, and a set S subset of V-2 such that C subset of V is an optimal r-identifying code in G if, and only if, C = A boolean OR S for some A is an element of A. This result gives a direct connection with induced subgraphs of Johnson graphs, which are graphs with vertex set a collection of k-subsets of V1, with edges between any two vertices sharing k - 1 elements.
Let G = (V, E) be a graph. For v is an element of V and r >= 1, we denote by B-G,B- r (v) the ball of radius r and centre v. A set C subset of V is said to be an r-identifying code if the sets B-G,B- r (v) boolean AND C, v is an element of 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 gamma(r)(G). We study the ensemble of all the different optimal r-identifying codes C, i.e., such that broken vertical bar C broken vertical bar = gamma(r)(G). We show that, given any collection A of k-subsets of V-1 = {1, 2, . . . , n}, there is a positive integer m, a graph G = (V, E) with V = V-1 boolean OR V-2, where V-2 = {n + 1, . . . , n + m}, and a set S subset of V-2 such that C subset of V is an optimal r-identifying code in G if, and only if, C = A boolean OR S for some A is an element of A. This result gives a direct connection with induced subgraphs of Johnson graphs, which are graphs with vertex set a collection of k-subsets of V1, with edges between any two vertices sharing k - 1 elements.
Downloadable publication This is an electronic reprint of the original article. |  |
UTU Research Portal