Improved bounds on the domination number of a tree

Wyatt J. Desormeaux, Teresa W. Haynes, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

13 Citations (Scopus)

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-n1+2)/3 is arbitrarily large. Further, the trees T satisfying sl(T)=(n-n1+2)/3 are characterized.

Original languageEnglish
Pages (from-to)88-94
Number of pages7
JournalDiscrete Applied Mathematics
Volume177
DOIs
Publication statusPublished - 20 Nov 2014

Keywords

  • Degree sequence
  • Domination
  • Slater number
  • Trees

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Improved bounds on the domination number of a tree'. Together they form a unique fingerprint.

Cite this