On the number of optimal identifying codes in a twin-free graph
| Autor: | Antoine Lobstein, Iiro S. Honkala, Olivier Hudry |
|---|---|
| Přispěvatelé: | Mathématiques discrètes, Codage et Cryptographie (MC2), Laboratoire Traitement et Communication de l'Information (LTCI), Institut Mines-Télécom [Paris] (IMT)-Télécom Paris-Institut Mines-Télécom [Paris] (IMT)-Télécom Paris, Département Informatique et Réseaux (INFRES), Télécom ParisTech |
| Rok vydání: | 2015 |
| Předmět: |
Discrete mathematics
Vertex (graph theory) Applied Mathematics ta111 Graph theory Free graph [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] 16. Peace & justice Graph Combinatorics [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] Discrete Mathematics and Combinatorics Bound graph Undirected graph ComputingMilieux_MISCELLANEOUS Mathematics |
| Zdroj: | Discrete Applied Mathematics Discrete Applied Mathematics, Elsevier, 2015, 180, pp.111-119 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2014.08.020 |
| Popis: | Let G be a simple, undirected graph with vertex set? V . For v ? V and r ? 1 , we denote by B G , r ( v ) the ball of radius? r and centre? v . A set C ? V is said to be an r -identifying code in? G if the sets B G , r ( v ) ? C , v ? 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? γ r I D ( G ) .We study the number of different optimal r -identifying codes C , i.e., such that | C | = γ r I D ( G ) , that a graph G can admit, and try to construct graphs having "many" such codes. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect