کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420202 683905 2011 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Open neighborhood locating–dominating in trees
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Open neighborhood locating–dominating in trees
چکیده انگلیسی

For a graph GG that models a facility or a multiprocessor network, detection devices can be placed at the vertices so as to identify the location of an intruder such as a thief or saboteur or a faulty processor. Open neighborhood locating–dominating sets are of interest when the intruder/fault at a vertex precludes its detection at that location. The parameter OLD(G) denotes the minimum cardinality of a vertex set S⊆V(G)S⊆V(G) such that for each vertex vv in V(G)V(G) its open neighborhood N(v)N(v) has a unique non-empty intersection with SS. For a tree TnTn of order nn we have ⌈n/2⌉+1≤OLD(Tn)≤n−1. We characterize the trees that achieve these extremal values.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 159, Issue 6, 28 March 2011, Pages 484–489
نویسندگان
, ,