A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On the number of optimal identifying codes in a twin-free graph
Tekijät: Iiro Honkala, Olivier Hudry, Antoine Lobstein
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2015
Journal: Discrete Applied Mathematics
Tietokannassa oleva lehden nimi: DISCRETE APPLIED MATHEMATICS
Lehden akronyymi: DISCRETE APPL MATH
Vuosikerta: 180
Aloitussivu: 111
Lopetussivu: 119
Sivujen määrä: 9
ISSN: 0166-218X
DOI: https://doi.org/10.1016/j.dam.2014.08.020
Let G be a simple, undirected graph with vertex set V. 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 in G 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 or r-identifiable, and in this case the smallest size of an r-identifying code in G is denoted by gamma(ID)(r)(G). We study the number of different optimal r-identifying codes C, i.e., such that vertical bar C vertical bar = gamma(ID)(r)(G), that a graph G can admit, and try to construct graphs having "many" such codes.