On Vertex-Robust Identifying Codes of Level Three




Honkala Iiro, Laihonen Tero

PublisherCHARLES BABBAGE RES CTR

2010

Ars Combinatoria

ARS COMBINATORIA

ARS COMBINATORIA

94

115

127

13

0381-7032

http://www.combinatorialmath.ca/arscombinatoria/vol94.html(external)

https://research.utu.fi/converis/portal/Publication/2042130(external)



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.

Last updated on 2024-26-11 at 22:21