Acyclic Domination Number and Minimum Degree in $2$-Diameter-Critical Graphs

Abstract

A subset $S$ of the vertex set of a graph $G$ is called acyclic if the subgraph it induces in $G$ contains no cycles. We call $S$ an acyclic dominating set if it is both acyclic and dominating. The minimum cardinality of an acyclic dominating set, denoted by ${\gamma }_a(G)$, is called the acyclic domination number of $G$. A graph $G$ is $2-diameter-critical$ if it has diameter $2$ and the deletion of any edge increases its diameter. In this paper, we show that for any positive integers $k$ and $d\ge 3$, there is a $2$-diameter-critical graph $G$ such that $\delta (G)=d$ and ${\gamma }_a(G)–\delta (G)\ge k$, and our result answers a question posed by Cheng et al. in negative.