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-n1+2)/3 is arbitrarily large. Further, the trees T satisfying sl(T)=(n-n1+2)/3 are characterized.
| Identifer | oai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-16920 |
| Date | 20 November 2014 |
| Creators | Desormeaux, Wyatt J., Haynes, Teresa W., Henning, Michael A. |
| Publisher | Digital Commons @ East Tennessee State University |
| Source Sets | East Tennessee State University |
| Detected Language | English |
| Type | text |
| Source | ETSU Faculty Works |
Page generated in 0.0021 seconds