کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419082 | 681741 | 2014 | 14 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Applied Mathematics - Volume 164, Part 1, 19 February 2014, Pages 20–33