Article ID Journal Published Year Pages File Type
421055 Discrete Applied Mathematics 2006 4 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,