Maximum size of a minimum watching system and the graphs achieving the bound

David Auger, Irène Charon, Olivier Hudry, Antoine Lobstein

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)20-33
Number of pages14
JournalDiscrete Applied Mathematics
Volume164
Issue numberPART 1
DOIs
Publication statusPublished - 1 Jan 2014
Externally publishedYes

Keywords

  • Graph theory
  • Identifying codes
  • Watching systems

Fingerprint

Dive into the research topics of 'Maximum size of a minimum watching system and the graphs achieving the bound'. Together they form a unique fingerprint.

Cite this