کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428505 686785 2015 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On Secure Domination in Graphs
ترجمه فارسی عنوان
در سلطه امن در نمودارها
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

A set D⊂VD⊂V of a graph G=(V,E)G=(V,E) is a dominating set of G if every vertex not in D is adjacent to at least one vertex in D. A secure dominating set S of a graph G   is a dominating set with the property that each vertex u∈V∖Su∈V∖S is adjacent to a vertex v∈Sv∈S such that (S∖{v})∪{u}(S∖{v})∪{u} is a dominating set. The secure domination number γs(G)γs(G) equals the minimum cardinality of a secure dominating set of G  . We first show that the problem of computing the secure domination number is NP-complete for bipartite and split graphs. Then we present bounds relating the secure domination number to the domination number γ(G)γ(G), the independence number β0(G)β0(G) and the independent domination number i(G)i(G). In particular, we prove that γs(G)≤γ(G)+β0(G)−1γs(G)≤γ(G)+β0(G)−1 if G   is an arbitrary graph, γs(G)≤32β0(G) if G   is triangle-free, and γs(G)≤β0(G)γs(G)≤β0(G) if G has girth at least six. Finally, we show for the class of trees T   that γs(T)≥i(T)γs(T)≥i(T) and γs(T)>β0(T)/2γs(T)>β0(T)/2. The last result answers the question posed by Mynhardt at the 22nd Clemson mini-Conference, 2007

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 115, Issue 10, October 2015, Pages 786–790
نویسندگان
, ,