On a new class of identifying codes in graphs



: Honkala I, Laihonen T

Publisher: ELSEVIER SCIENCE BV

: 2007

: Information Processing Letters

: INFORMATION PROCESSING LETTERS

: INFORM PROCESS LETT

: 102

: 2-3

: 92

: 98

: 7

: 0020-0190

DOI: https://doi.org/10.1016/j.ipl.2006.11.007(external)


Assume that G = (V, E) is an undirected graph, and C subset of V. For every v is an element of V, we denote 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 from u to v. For every F subset of V, we denote I-r(F) = boolean OR(v is an element of F) I-r(v). We study codes C with the property that if I-r(F) = I-r(F') and F not equal F', then both F and F' have size at least l + 1. Such codes can be used in the maintenance of multiprocessor architectures. We consider the cases when G is the infinite square or king grid, infinite triangular lattice or hexagonal mesh, or a binary hypercube. (c) 2006 Elsevier B.V. All rights reserved.



Last updated on 2024-26-11 at 14:14