A1 Refereed original research article in a scientific journal
On a new class of identifying codes in graphs
Authors: Honkala I, Laihonen T
Publisher: ELSEVIER SCIENCE BV
Publication year: 2007
Journal: Information Processing Letters
Journal name in source: INFORMATION PROCESSING LETTERS
Journal acronym: INFORM PROCESS LETT
Volume: 102
Issue: 2-3
First page : 92
Last page: 98
Number of pages: 7
ISSN: 0020-0190
DOI: https://doi.org/10.1016/j.ipl.2006.11.007(external)
Abstract
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.
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.
UTU Research Portal