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. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1016/j.disc.2017.02.009 | Discrete Mathematics |
Keywords | Field | DocType |
Domination,Slater number,Sparse graphs,Outerplanar graphs,Paired domination,Total domination | Graph,Discrete mathematics,Combinatorics,Outerplanar graph,Upper and lower bounds,Degree (graph theory),Domination analysis,Real number,Mathematics | Journal |
Volume | Issue | ISSN |
340 | 7 | 0012-365X |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Michael Gentner | 1 | 22 | 4.46 |
Dieter Rautenbach | 2 | 946 | 138.87 |