DOI: 10.7494/opmath.2008.28.3.331 ISSN: 1232-9274

On equality in an upper bound for the acyclic domination number

Vladimir Samodivkin
Show PDF Cite

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.

More from our Archive