کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5776834 | 1413643 | 2017 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Reconfiguring dominating sets in some well-covered and other classes of graphs
ترجمه فارسی عنوان
تنظیم مجدد مجموعه های غالب در برخی از کلاس های تحت پوشش و سایر کلاس ها
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مشکلات تصحیح تسلط بر گراف، مجموعه مستقل،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
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
Journal: Discrete Mathematics - Volume 340, Issue 8, August 2017, Pages 1802-1817
نویسندگان
R. Haas, K. Seyffarth,