کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
421137 684147 2014 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Global security in claw-free cubic graphs
ترجمه فارسی عنوان
امنیت جهانی در گرافیک مکعبی بدون نقاشی
کلمات کلیدی
مجموعه امن، غرور مجموعه، نمودار مکعبی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

A secure set   in a graph G=(V,E)G=(V,E) is a set of vertices S⊆VS⊆V such that for any subset X⊆SX⊆S, |N[X]∩S|≥|N(X)−S||N[X]∩S|≥|N(X)−S|. A global secure set  SD⊆VSD⊆V is a secure set that is also a dominating set, i.e., N[SD]=VN[SD]=V. In this paper we investigate global secure sets that contain exactly half of the vertices of the graph. In particular we show that every hamiltonian claw-free cubic graph has such a global secure set. Moreover, we prove that in any claw-free cubic graph there is a global secure set that contains at most 5/95/9 of the vertices of the graph.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 175, 1 October 2014, Pages 11–23
نویسندگان
, ,