A1 Refereed original research article in a scientific journal
On Vertex-Robust Identifying Codes of Level Three
Authors: Honkala Iiro, Laihonen Tero
Publisher: CHARLES BABBAGE RES CTR
Publication year: 2010
Journal: Ars Combinatoria
Journal name in source: ARS COMBINATORIA
Journal acronym: ARS COMBINATORIA
Volume: 94
First page : 115
Last page: 127
Number of pages: 13
ISSN: 0381-7032
Web address : http://www.combinatorialmath.ca/arscombinatoria/vol94.html(external)
Self-archived copy’s web address: https://research.utu.fi/converis/portal/Publication/2042130(external)
Abstract
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.
Downloadable publication This is an electronic reprint of the original article. |  |
UTU Research Portal