@Article{Samodivkin2008,
author = "Samodivkin, Vladimir",
title = "On equality in an upper bound for the acyclic domination number",
journal = "Opuscula Math.",
year = "2008",
volume = "28",
number = "3",
pages = "331--334",
doi = "http://dx.doi.org/10.7494/OpMath.2008.28.3.331",
url = "http://dx.doi.org/10.7494/OpMath.2008.28.3.331",
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.",
keywords = "dominating set, acyclic set, independent set, acyclic domination number",
issn = "1232-9274"
}