Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419998 | Discrete Applied Mathematics | 2013 | 12 Pages |
Abstract
We introduce the notion of watching systems in graphs, which is a generalization of that of identifying codes. We give some basic properties of watching systems, an upper bound on the minimum size of a watching system, and results on the graphs which achieve this bound; we also study the cases of the paths and cycles, and give complexity results.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
David Auger, Irène Charon, Olivier Hudry, Antoine Lobstein,