A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

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




TekijätIiro Honkala, Olivier Hudry, Antoine Lobstein

KustantajaELSEVIER SCIENCE BV

Julkaisuvuosi2015

JournalDiscrete Applied Mathematics

Tietokannassa oleva lehden nimiDISCRETE APPLIED MATHEMATICS

Lehden akronyymiDISCRETE APPL MATH

Vuosikerta180

Aloitussivu111

Lopetussivu119

Sivujen määrä9

ISSN0166-218X

DOIhttps://doi.org/10.1016/j.dam.2014.08.020


Tiivistelmä

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.




Last updated on 2024-26-11 at 19:54