Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 1019-1022 |
Number of pages | 4 |
Journal | Discrete Applied Mathematics |
Volume | 154 |
Issue number | 6 |
DOIs | |
Publication status | Published - 15 Apr 2006 |
Keywords
- Acyclic domination number
- Diameter two
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics