A note on acyclic domination number in graphs of diameter two
A subset S S of the vertex set of a graph G G is called acyclic  if the subgraph it induces in G G contains no cycles. S S is called an acyclic dominating  set of G G if it is both acyclic and dominating. The minimum cardinality of an acyclic dominating set, denoted by ?a(G) ? a ( G ) , is called the acyclic domination number  of G G . Hedetniemi et al. [Acyclic domination, Discrete Math. 222 (2000) 151165] introduced the concept of acyclic domination and posed the following open problem: if ?(G) ? ( G ) is the minimum degree of G G , is ?a(G)??(G) ? 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 k , there is a graph G G with diameter two such that ?a(G)-?(G)?k ? a ( G ) - ? ( G ) ? k .
acyclic domination number diameter two