کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949891 | 1364262 | 2017 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Minimal dominating sets in interval graphs and trees
ترجمه فارسی عنوان
مجموعه های غالب مینیمم در گراف ها و درختان فاصله
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودارها، مجموعه های ممانعت کننده کلاس های گراف، شمارش
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We show that interval graphs on n vertices have at most 3n/3â1.4422n minimal dominating sets, and that these can be enumerated in time Oâ(3n/3). As there are examples of interval graphs that actually have 3n/3 minimal dominating sets, our bound is tight. We show that the same upper bound holds also for trees, i.e. trees on n vertices have at most 3n/3â1.4422n minimal dominating sets. The previous best upper bound on the number of minimal dominating sets in trees was 1.4656n, and there are trees that have 1.4167n minimal dominating sets. Hence our result narrows this gap. On general graphs there is a larger gap, with 1.7159n being the best known upper bound, whereas no graph with 1.5705n or more minimal dominating sets is known.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 162-170
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 162-170
نویسندگان
Petr A. Golovach, Pinar Heggernes, Mamadou Moustapha Kanté, Dieter Kratsch, Yngve Villanger,