Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5776902 | Discrete Mathematics | 2017 | 6 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Michael Gentner, Dieter Rautenbach,