Improved bounds on the domination number of a tree

A dominating set in a graph GG is a set SS of vertices of GG such that every vertex not in SS is adjacent to a vertex of SS. The domination number γ(G)γ(G) of GG is the minimum cardinality of a dominating set of GG. The Slater number sℓ(G)sℓ(G) is the smallest integer tt such that tt added to the sum of the first tt terms of the non-increasing degree sequence of GG is at least as large as the number of vertices of GG. It is well-known that γ(G)≥sℓ(G)γ(G)≥sℓ(G). If GG has nn vertices with minimum degree  δ≥1δ≥1 and maximum degree  ΔΔ, then we show that ⌈n/(Δ+1)⌉≤sℓ(G)≤⌈n/(δ+1)⌉⌈n/(Δ+1)⌉≤sℓ(G)≤⌈n/(δ+1)⌉. Let TT be a tree on n≥3n≥3 vertices with n1n1 vertices of degree  11. We prove that γ(T)≤3sℓ(T)−2γ(T)≤3sℓ(T)−2, and we characterize the trees that achieve equality in this bound. Lemanska (2004) proved that γ(T)≥(n−n1+2)/3γ(T)≥(n−n1+2)/3. We improve this result by showing that sℓ(T)≥(n−n1+2)/3sℓ(T)≥(n−n1+2)/3 and establishing the existence of trees TT for which the difference between the Slater number sℓ(T)sℓ(T) and (n−n1+2)/3(n−n1+2)/3 is arbitrarily large. Further, the trees TT satisfying sℓ(T)=(n−n1+2)/3sℓ(T)=(n−n1+2)/3 are characterized.