Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Maximum Size of a Minimum Watching System and the Graphs Achieving the Bound

David Auger 1 Irène Charon 2 Olivier Hudry 2 Antoine Lobstein 2, 3 
1 MAGMAT
LTCI - Laboratoire Traitement et Communication de l'Information, Télécom ParisTech
Abstract : 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 diff erent 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 watcher w belonging to 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-00680690
Contributor : Olivier Hudry Connect in order to contact the contributor
Submitted on : Monday, March 19, 2012 - 9:39:43 PM
Last modification on : Monday, January 24, 2022 - 11:43:20 AM
Long-term archiving on: : Wednesday, June 20, 2012 - 2:35:09 AM

File

Watching_systems_ACHL_HAL_mars...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00680690, version 1

Citation

David Auger, Irène Charon, Olivier Hudry, Antoine Lobstein. Maximum Size of a Minimum Watching System and the Graphs Achieving the Bound. 2012. ⟨hal-00680690⟩

Share

Metrics

Record views

138

Files downloads

127