Watching Systems in Graphs: an Extension of Identifying Codes
Discrete Applied Mathematics, Vol. 161, pp. 1674-1685, 2013.
David AUGER, Irène CHARON, Olivier HUDRY & Antoine LOBSTEIN
Centre National de la Recherche Scientifique
Ecole Nationale Supérieure des Télécommunications
46 rue Barrault, 75634 Paris cédex 13, France
{david.auger, irene.charon, olivier.hudry, antoine.lobstein}@telecom-paristech.fr
Résumé. 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.