Maximum Size of a Minimum Watching System and the Graphs Achieving the Bound
Discrete Applied Mathematics, Vol. 164, pp. 20-33, 2014.
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é. Let G = (V(G), E(G)) be an undirected graph. A watcher w of G is a couple w = (l(w), A(w)), where l(w) belongs to V(G) and A(w) is a set of vertices of G at distance 0 or 1 from l(w). If a vertex v belongs to A(w), we say that v is covered by w. Two vertices v1 and v2 in G are said to be separated by a set of watchers if the list of the watchers covering v1 is different from that of v2. We say that a set W of watchers is a watching system for G if every vertex v is covered by at least one w in W, and any two vertices v1, v2 are separated by W. The minimum number of watchers necessary to watch G is denoted by w(G). We give an upper bound on w(G) for connected graphs of order n and characterize the trees achieving this bound, before studying the more complicated characterization of the connected graphs achieving this bound.