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.