Passer à la navigation principale Passer à la recherche Passer au contenu principal

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

  • CNRS LTCI

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

5 Citations (Scopus)

Résumé

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.

langue originaleAnglais
Pages (de - à)20-33
Nombre de pages14
journalDiscrete Applied Mathematics
Volume164
Numéro de publicationPART 1
Les DOIs
étatPublié - 1 janv. 2014
Modification externeOui

Empreinte digitale

Examiner les sujets de recherche de « Maximum size of a minimum watching system and the graphs achieving the bound ». Ensemble, ils forment une empreinte digitale unique.

Contient cette citation