کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5776834 1413643 2017 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Reconfiguring dominating sets in some well-covered and other classes of graphs
ترجمه فارسی عنوان
تنظیم مجدد مجموعه های غالب در برخی از کلاس های تحت پوشش و سایر کلاس ها
کلمات کلیدی
مشکلات تصحیح تسلط بر گراف، مجموعه مستقل،
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Let G be a graph and let k be a positive integer. The k-dominating graph of G, denoted by Dk(G), has vertices corresponding to the dominating sets of G having cardinality at most k; two vertices of Dk(G) are adjacent if and only if the dominating set corresponding to one of the vertices can be obtained from the dominating set corresponding to the second vertex by the addition or deletion of a single vertex. We denote by d0(G) the least value of k for which Dk(G) is connected for all k≥d0(G). It is known that d0(G)≥Γ(G)+1, where Γ(G) is the upper domination number of G. In this paper we prove that if G is a graph that is both perfect and irredundant perfect, or if G belongs to certain classes of well-covered graphs, then d0(G)=Γ(G)+1. In order to prove these results, we show that all independent dominating sets of a graph G are in the same component of DΓ(G)+1(G).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 340, Issue 8, August 2017, Pages 1802-1817
نویسندگان
, ,