A subset S of the vertex set of a graph G is called acyclic if the subgraph it induces in G contains no cycles. S is called an acyclic dominating set of G if it is both acyclic and dominating. The minimum cardinality of an acyclic dominating set, denoted by γa(G), is called the acyclic domination number of G. Hedetniemi et al. [Acyclic domination, Discrete Math. 222 (2000) 151-165] introduced the concept of acyclic domination and posed the following open problem: if δ(G) is the minimum degree of G, is γa(G)≤δ(G) for any graph whose diameter is two? In this paper, we provide a negative answer to this question by showing that for any positive k, there is a graph G with diameter two such that γa(G)-δ(G)≥k.
- Acyclic domination number
- Diameter two
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics