Relating the annihilation number and the 2-domination number for unicyclic graphs

Xinying Hua


The \emph{2-domination number} $\gamma_2(G)$ of a graph $G$ is the minimum cardinality of a set $S\subseteq V(G)$ such that every vertex from $V(G)\setminus S$ is adjacent to at least two vertices in $S$. The \emph{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 its edges. It was conjectured that $\gamma_2(G)\le a(G)+1$ holds for every non-trivial connected graph $G$. The conjecture was earlier confirmed for graphs of minimum degree 3, trees, block graphs and some bipartite cacti. However, a class of cacti were found as counterexample graphs recently by Yue et al.~\cite{Yue} to the above conjecture. In this paper, we consider the above conjecture from the positive side and prove that this conjecture holds for all unicyclic graphs.


  • There are currently no refbacks.