A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
A family of optimal identifying codes in Z(2)
Tekijät: Honkala I
Kustantaja: ACADEMIC PRESS INC ELSEVIER SCIENCE
Julkaisuvuosi: 2006
Journal: Journal of Combinatorial Theory, Series A
Tietokannassa oleva lehden nimi: JOURNAL OF COMBINATORIAL THEORY SERIES A
Lehden akronyymi: J COMB THEORY A
Vuosikerta: 113
Numero: 8
Aloitussivu: 1760
Lopetussivu: 1763
Sivujen määrä: 4
ISSN: 0097-3165
DOI: https://doi.org/10.1016/j.jcta.2006.03.011
Tiivistelmä
Assume that G = (V, E) is a simple undirected graph, and C is a nonempty subset of V. For every upsilon is an element of V, we denote I-r(upsilon) = {u is an element of C vertical bar d(G) (u, upsilon) <= r}, where d(G) (u, upsilon) denotes the number of edges on any shortest path between u and v. If the sets Ir(v) for V E V are pairwise different, and none of them is the empty set, we say that C is an r-identifying code in G. If C is r-identifying in every graph G' that can be obtained by adding and deleting edges in such a way that the number of additions and deletions together is at most t, the code C is called t-edge-robust. Let K be the graph with vertex set Z(2) in which two different vertices are adjacent if their Euclidean distance is at most root 2. We show that the smallest possible density of a 3-edge-robust code in K is r+1/2r+1 for all r > 2. (c) 2006 Elsevier Inc. All rights reserved.
Assume that G = (V, E) is a simple undirected graph, and C is a nonempty subset of V. For every upsilon is an element of V, we denote I-r(upsilon) = {u is an element of C vertical bar d(G) (u, upsilon) <= r}, where d(G) (u, upsilon) denotes the number of edges on any shortest path between u and v. If the sets Ir(v) for V E V are pairwise different, and none of them is the empty set, we say that C is an r-identifying code in G. If C is r-identifying in every graph G' that can be obtained by adding and deleting edges in such a way that the number of additions and deletions together is at most t, the code C is called t-edge-robust. Let K be the graph with vertex set Z(2) in which two different vertices are adjacent if their Euclidean distance is at most root 2. We show that the smallest possible density of a 3-edge-robust code in K is r+1/2r+1 for all r > 2. (c) 2006 Elsevier Inc. All rights reserved.
Turun yliopiston Tutkimustietojärjestelmän portaali