HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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

136

Files downloads

122