Abstract
Let G=(V(G),E(G)) be an undirected graph. A watcher w of G is a couple w = (ℓ(w), A(w)), where ℓ(w) belongs to V(G) and A(w) is a set of vertices of G at distance 0 or 1 from ℓ(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∈W, and every 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 attaining this bound, before studying the more complicated characterization of the connected graphs attaining this bound.
| Original language | English |
|---|---|
| Pages (from-to) | 20-33 |
| Number of pages | 14 |
| Journal | Discrete Applied Mathematics |
| Volume | 164 |
| Issue number | PART 1 |
| DOIs | |
| Publication status | Published - 1 Jan 2014 |
| Externally published | Yes |
Keywords
- Graph theory
- Identifying codes
- Watching systems