کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419082 681741 2014 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Maximum size of a minimum watching system and the graphs achieving the bound
ترجمه فارسی عنوان
حداکثر اندازه حداقل سیستم تماشا و گراف به دست آوردن محدود
کلمات کلیدی
نظریه گراف، سیستم های مشاهده کد شناسایی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Let G=(V(G),E(G))G=(V(G),E(G)) be an undirected graph. A watcher ww of  GG is a couple ww = (ℓ(w)ℓ(w), A(w)A(w)), where ℓ(w)ℓ(w) belongs to  V(G)V(G) and A(w)A(w)  is a set of vertices of  GG at distance 0 or 1 from  ℓ(w)ℓ(w). If a vertex vv belongs to  A(w)A(w), we say that vv is covered by  ww. Two vertices v1v1 and  v2v2 in  GG are said to be separated by a set of watchers if the list of the watchers covering  v1v1 is different from that of  v2v2. We say that a set  WW of watchers is a watching system for  GG if every vertex  vv is covered by at least one  w∈Ww∈W, and every two vertices v1,v2v1,v2 are separated by  WW. The minimum number of watchers necessary to watch  GG is denoted by  w(G)w(G). We give an upper bound on  w(G)w(G) for connected graphs of order  nn and characterize the trees attaining this bound, before studying the more complicated characterization of the connected graphs attaining this bound.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 164, Part 1, 19 February 2014, Pages 20–33
نویسندگان
, , , ,