A1 Refereed original research article in a scientific journal

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




AuthorsIiro Honkala, Olivier Hudry, Antoine Lobstein

PublisherELSEVIER SCIENCE BV

Publication year2015

JournalDiscrete Applied Mathematics

Journal name in sourceDISCRETE APPLIED MATHEMATICS

Journal acronymDISCRETE APPL MATH

Volume180

First page 111

Last page119

Number of pages9

ISSN0166-218X

DOIhttps://doi.org/10.1016/j.dam.2014.08.020(external)


Abstract

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