Browsing by Author "Samodivkin, Vladimir"

Now showing 1 - 1 of 1

Access status: Open Access ,
On equality in an upper bound for the acyclic domination number
(2008) Samodivkin, Vladimir
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.