Article ID Journal Published Year Pages File Type
419082 Discrete Applied Mathematics 2014 14 Pages PDF
Abstract

Let G=(V(G),E(G))G=(V(G),E(G)) be an undirected graph. A watcher ww of  GG is a couple ww = (ℓ(w)ℓ(w), A(w)A(w)), where ℓ(w)ℓ(w) belongs to  V(G)V(G) and A(w)A(w)  is a set of vertices of  GG at distance 0 or 1 from  ℓ(w)ℓ(w). If a vertex vv belongs to  A(w)A(w), we say that vv is covered by  ww. Two vertices v1v1 and  v2v2 in  GG are said to be separated by a set of watchers if the list of the watchers covering  v1v1 is different from that of  v2v2. We say that a set  WW of watchers is a watching system for  GG if every vertex  vv is covered by at least one  w∈Ww∈W, and every two vertices v1,v2v1,v2 are separated by  WW. The minimum number of watchers necessary to watch  GG is denoted by  w(G)w(G). We give an upper bound on  w(G)w(G) for connected graphs of order  nn and characterize the trees attaining this bound, before studying the more complicated characterization of the connected graphs attaining this bound.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,