A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On Vertex-Robust Identifying Codes of Level Three
Tekijät: Honkala Iiro, Laihonen Tero
Kustantaja: CHARLES BABBAGE RES CTR
Julkaisuvuosi: 2010
Journal: Ars Combinatoria
Tietokannassa oleva lehden nimi: ARS COMBINATORIA
Lehden akronyymi: ARS COMBINATORIA
Vuosikerta: 94
Aloitussivu: 115
Lopetussivu: 127
Sivujen määrä: 13
ISSN: 0381-7032
Verkko-osoite: http://www.combinatorialmath.ca/arscombinatoria/vol94.html
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/Publication/2042130
Tiivistelmä
Assume that G = (V, E) is an undirected and connected graph, and consider C subset of V. For every v is an element of V, let I(r)(v) = {u is an element of C : d(u, v) <= r}, where d(u, v) denotes the number of edges on any shortest path between u to v in G. If all the sets I(r)(v) for v is an element of V are pairwise different, and none of them is the empty set, C is called an r-identifying code. In this paper, we consider t-vertex-robust r-identifying codes of level s, that is, r-identifying codes such that they cover every vertex at least s times and the code is vertex-robust in the sense that vertical bar I(r)(u) Delta I(r)(v)vertical bar >= 2t+1 for any two different vertices u and v. Vertex-robust identifying codes of different levels are examined, in particular, of level 3. We give bounds (sometimes exact values) on the density or cardinality of the codes in binary hypercubes and in some infinite grids.
Assume that G = (V, E) is an undirected and connected graph, and consider C subset of V. For every v is an element of V, let I(r)(v) = {u is an element of C : d(u, v) <= r}, where d(u, v) denotes the number of edges on any shortest path between u to v in G. If all the sets I(r)(v) for v is an element of V are pairwise different, and none of them is the empty set, C is called an r-identifying code. In this paper, we consider t-vertex-robust r-identifying codes of level s, that is, r-identifying codes such that they cover every vertex at least s times and the code is vertex-robust in the sense that vertical bar I(r)(u) Delta I(r)(v)vertical bar >= 2t+1 for any two different vertices u and v. Vertex-robust identifying codes of different levels are examined, in particular, of level 3. We give bounds (sometimes exact values) on the density or cardinality of the codes in binary hypercubes and in some infinite grids.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
Turun yliopiston Tutkimustietojärjestelmän portaali