Watching systems in graphs: an extension of identifying codes

David Auger (1) , Irène Charon (2, 3) , Olivier Hudry (2, 3) , Antoine Lobstein (2, 3)

1 MAGMAT
2 Télécom ParisTech
3 LTCI - Laboratoire Traitement et Communication de l'Information

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.

Mots clés: Graph theory; Complexity; Identifying codes; Watching systems; Paths; Cycles

Domaines: Mathématique discrète [cs.DM]

David Auger, Irène Charon, Olivier Hudry, Antoine Lobstein. Watching systems in graphs: an extension of identifying codes. 2010. ⟨hal-00481469⟩