Opuscula Math. 28, no. 3 (2008), 331-334
Opuscula Mathematica
On equality in an upper bound for the acyclic domination number
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.
Mathematics Subject Classification: 05C69.
- Vladimir Samodivkin
- University of Architecture Civil Engineering and Geodesy, Department of Mathematics, Hristo Smirnenski 1 Blv., 1046 Sofia, Bulgaria
- Received: 2007-06-11.
- Accepted: 2008-01-15.
