Maximum Size of a Minimum Watching System and the Graphs Achieving the Bound
Résumé
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.
Domaines
Mathématique discrète [cs.DM]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...