کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5776902 | 1413645 | 2017 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Some comments on the Slater number
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Let G be a graph with degree sequence d1â¥â¯â¥dn. Slater proposed sâ(G)=min{s:(d1+1)+â¯+(ds+1)â¥n} as a lower bound on the domination number γ(G) of G. We show that deciding the equality of γ(G) and sâ(G) for a given graph G is NP-complete but that one can decide efficiently whether γ(G)>sâ(G) or γ(G)â¤lnn(G)sâ(G)+1sâ(G). For real numbers α and β with αâ¥max{0,β}, let G(α,β) be the class of non-null graphs G such that every non-null subgraph H of G has at most αn(H)âβ many edges. Generalizing a result of Desormeaux, Haynes, and Henning, we show that γ(G)â¤(2α+1)sâ(G)â2β for every graph G in G(α,β) with αâ¤32. Furthermore, we show that γ(G)âsâ(G) is bounded for graphs G in G(α,β) if and only if α<2. For an outerplanar graph G with sâ(G)â¥2, we show γ(G)â¤6sâ(G)â6. In analogy to sâ(G), we propose sât(G)=min{s:d1+â¯+dsâ¥n} as a lower bound on the total domination number. Strengthening results due to Raczek as well as Chellali and Haynes, we show that sât(T)â¥n+2ân12 for every tree T of order n at least 2 with n1 endvertices.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 340, Issue 7, July 2017, Pages 1497-1502
Journal: Discrete Mathematics - Volume 340, Issue 7, July 2017, Pages 1497-1502
نویسندگان
Michael Gentner, Dieter Rautenbach,