کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647126 | 1342329 | 2016 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Bounds on the maximum number of minimum dominating sets
ترجمه فارسی عنوان
محدودیت های حداکثر تعداد حداقل مجموعه های حاکم بر
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
غالب مجموعه ها، تعداد سلطه
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Given a graph with domination number γγ, we find bounds on the maximum number of minimum dominating sets. First, for γ≥3γ≥3, we obtain lower bounds on the number of γγ-sets that do not dominate a graph on nn vertices. Then, we show that γγ-fold lexicographic product of the complete graph on n1/γn1/γ vertices has domination number γγ and nγ−O(nγ−1γ) dominating sets of size γγ. Finally, we see that a certain random graph has, with high probability, (i) domination number γγ; and (ii) all but o(nγ)o(nγ) of its γγ-sets being dominating.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 5, 6 May 2016, Pages 1537–1542
Journal: Discrete Mathematics - Volume 339, Issue 5, 6 May 2016, Pages 1537–1542
نویسندگان
Samuel Connolly, Zachary Gabor, Anant Godbole, Bill Kay, Thomas Kelly,