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.

Full text (pdf)

• University of Architecture Civil Engineering and Geodesy, Department of Mathematics, Hristo Smirnenski 1 Blv., 1046 Sofia, Bulgaria