|
Bounding the domination number of a tree in terms of its annihilation numberKeywords: annihilation number , dominating set , domination number Abstract: 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 $nge 2$, $gamma(T)le frac{3a(T)+2}{4}$, and we characterize the trees achieving this bound.
|