کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421055 | 684022 | 2006 | 4 صفحه PDF | دانلود رایگان |

A subset SS of the vertex set of a graph GG is called acyclic if the subgraph it induces in GG contains no cycles. SS is called an acyclic dominating set of GG 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 GG. 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)δ(G) is the minimum degree of GG, 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 kk, there is a graph GG with diameter two such that γa(G)-δ(G)⩾kγa(G)-δ(G)⩾k.
Journal: Discrete Applied Mathematics - Volume 154, Issue 6, 15 April 2006, Pages 1019–1022