Back to Search
Start Over
A note on acyclic domination number in graphs of diameter two
- Source :
-
Discrete Applied Mathematics . Apr2006, Vol. 154 Issue 6, p1019-1022. 4p. - Publication Year :
- 2006
-
Abstract
- Abstract: A subset of the vertex set of a graph is called acyclic if the subgraph it induces in contains no cycles. is called an acyclic dominating set of if it is both acyclic and dominating. The minimum cardinality of an acyclic dominating set, denoted by , is called the acyclic domination number of . Hedetniemi et al. [Acyclic domination, Discrete Math. 222 (2000) 151–165] introduced the concept of acyclic domination and posed the following open problem: if is the minimum degree of , is for any graph whose diameter is two? In this paper, we provide a negative answer to this question by showing that for any positive , there is a graph with diameter two such that . [Copyright &y& Elsevier]
- Subjects :
- *GRAPH theory
*NUMBER theory
*MATHEMATICS
*CARDINAL numbers
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 154
- Issue :
- 6
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 20032773
- Full Text :
- https://doi.org/10.1016/j.dam.2005.09.012