## Abstract

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

Original language | English |
---|---|

Pages (from-to) | 88-94 |

Number of pages | 7 |

Journal | Discrete Applied Mathematics |

Volume | 177 |

DOIs | |

Publication status | Published - 20 Nov 2014 |

## Keywords

- Degree sequence
- Domination
- Slater number
- Trees

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics