科研之友
微信
新浪微博
Facebook
分享链接
摘要
A subset S of the vertex set of a graph G is called acyclic if the subgraph it induces in G contains no cycles. We call S an acyclic dominating set if it is both acyclic and dominating. The minimum cardinality of an acyclic dominating set, denoted by gamma a(G), is called the acyclic domination number of G. A graph G is 2-diameter-critical if it has diameter 2 and the deletion of any edge increases its diameter. In this paper, we show that for any positive integers k and d >= 3, there is a 2-diameter-critical graph G such that delta(G) = d and gamma a(G) - gamma(G) >= k, and our result answers a question posed by Cheng et al. in negative.
- 出版日期2008-1
- 单位南京大学
