Communications of the
Korean Mathematical Society CKMS

Chellai et al.~\cite{1} gave an upper bound on the $[1, 2]$-domination number of tree and posed an open question ``how to classify trees satisfying the sharp bound?". Yang and Wu ~\cite{5} gave a partial solution for tree of order $n$ with $\ell$-leaves such that every non-leaf vertex has degree at least 4. In this paper, we give a new upper bound on the $[1, 2]$-domination number of tree which extends the result of Yang and Wu. In addition, we design a polynomial time algorithm for solving the open question. By using this algorithm, we give a characterization on the $[1, 2]$-domination number for trees of order $n$ with $\ell$ leaves satisfying $n-\ell$. Thereby, the open question posed by Chellai et al. is solved.

Keywords: $[1, 2]$-domination number, tree, polynomial algorithm

MSC numbers: 05C69, 05C85