On the ensemble of optimal dominating and locating-dominating codes in a graph
| Autor: | Antoine Lobstein, Olivier Hudry, Iiro S. Honkala |
|---|---|
| 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 |
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: |
Discrete mathematics
Vertex (graph theory) ta113 Graph theory [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] 16. Peace & justice Graph Computer Science Applications Theoretical Computer Science Combinatorics Dominating set [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] Signal Processing Undirected graph ComputingMilieux_MISCELLANEOUS Information Systems Mathematics |
| Zdroj: | Information Processing Letters Information Processing Letters, 2015, 115, pp.699-702 |
| ISSN: | 0020-0190 |
| DOI: | 10.1016/j.ipl.2015.04.005 |
| Popis: | Let G be a simple, undirected graph with vertex set V. For every v � V , we denote by N ( v ) the set of neighbours of v, and let N v ] = N ( v ) � { v } . A set C � V is said to be a dominating code in G if the sets N v ] � C , v � V , are all nonempty. A set C � V is said to be a locating-dominating code in G if the sets N v ] � C , v � V � C , are all nonempty and distinct. The smallest size of a dominating (resp., locating-dominating) code in G is denoted by d ( G ) (resp., � ( G ) ).We study the ensemble of all the different optimal dominating (resp., locating-dominating) codes C, i.e., such that | C | = d ( G ) (resp., | C | = � ( G ) ) in a graph G, and strongly link this problem to that of induced subgraphs of Johnson graphs. We study the set of all optimal locating-dominating codes in a given graph.There is a strong link between such sets and induced subgraphs of Johnson graphs.Instead of locating-dominating codes we also consider dominating codes. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect