On the ensemble 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
Computer Networks and Communications Applied Mathematics 010102 general mathematics Graph theory 0102 computer and information sciences Free graph [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] 01 natural sciences Graph Vertex (geometry) Combinatorics New digraph reconstruction conjecture Computational Theory and Mathematics 010201 computation theory & mathematics [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] Ball (mathematics) 0101 mathematics ComputingMilieux_MISCELLANEOUS Mathematics |
Zdroj: | Cryptography and Communications-Discrete Structures, Boolean Functions and Sequences Cryptography and Communications-Discrete Structures, Boolean Functions and Sequences, 2016, 8, pp.139-153 |
ISSN: | 1936-2455 1936-2447 |
DOI: | 10.1007/s12095-015-0148-3 |
Popis: | Let G = (V, E) be a graph. For v ? V and r ? 1, we denote by BG,r(v) the ball of radius r and centre v. A set C⊆V$C \subseteq V$ is said to be an r-identifying code if the sets BG,r(v)?C$B_{G,r}(v)\cap C$, v ? V, are all nonempty and distinct. A graph G which admits an r-identifying code is called r-twin-free, and in this case the smallest size of an r-identifying code is denoted by ?r(G). We study the ensemble of all the different optimalr-identifying codes C, i.e., such that |C| = ?r(G). We show that, given any collection A$\mathcal {A}$ of k-subsets of V1={1,2,?,n}, there is a positive integer m, a graph G = (V, E) with V=V1?V2$V=V_{1}\cup V_{2}$, where V2 = {n + 1 ,?, n + m}, and a set S⊆V2$S\subseteq V_{2}$ such that C⊆V$C\subseteq V$ is an optimal r-identifying code in G if, and only if, C=A?S$C=A\cup S$ for some A?A$A\in \mathcal {A}$. This result gives a direct connection with induced subgraphs of Johnson graphs, which are graphs with vertex set a collection of k-subsets of V1, with edges between any two vertices sharing k?1 elements. |
Databáze: | OpenAIRE |
Externí odkaz: |