Bounding the domination number of a tree in terms of its annihilation number
نویسندگان
1 Azarbaijan Shahid Madani University
2 Azarbaijan Shahid Madani University
3 Azarbaijan University of Tarbiat Moallem
doi
10.22108/toc.2013.2652چکیده
A set $S$ of vertices in a graph $G$ is a dominating set if every vertex of $V-S$ is adjacent to some vertex in $S$. The domination number $\gamma(G)$ is the minimum cardinality of a dominating set in $G$. The annihilation number $a(G)$ is the largest integer $k$ such that the sum of the first $k$ terms of the non-decreasing degree sequence of $G$ is at most the number of edges in $G$. In this paper, we show that for any tree $T$ of order $n\ge 2$, $\gamma(T)\le \frac{3a(T)+2}{4}$, and we characterize the trees achieving this bound.
