On equality in an upper bound for the acyclic domination number

Abstract

A subset $A$ of vertices in a graph $G$ is acyclic if the subgraph it induces contains no cycles. The acyclic domination number $\gamma_a(G)$ of a graph $G$ is the minimum cardinality of an acyclic dominating set of $G$. For any graph $G$ with $n$ vertices and maximum degree $\Delta(G)$, $\gamma_a(G) \leq n - \Delta(G)$. In this paper we characterize the connected graphs and the connected triangle-free graphs which achieve this upper bound.