TY  - JOUR
ID  - Samodivkin2008
LB  - Samodivkin2008
AU  - Samodivkin, Vladimir
TI  - On equality in an upper bound for the acyclic domination number
ST  - On equality in an upper bound for the acyclic domination number
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2008
VL  - 28
IS  - 3
SP  - 331
EP  - 334
DO  - http://dx.doi.org/10.7494/OpMath.2008.28.3.331
UR  - http://dx.doi.org/10.7494/OpMath.2008.28.3.331
AB  - 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.
KW  - dominating set
KW  - acyclic set
KW  - independent set
KW  - acyclic domination number
SN  - 1232-9274
ER  -