A note on acyclic domination number in graphs of diameter two

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

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 languageEnglish
Pages (from-to)1019-1022
Number of pages4
JournalDiscrete Applied Mathematics
Volume154
Issue number6
DOIs
Publication statusPublished - 15 Apr 2006

Keywords

  • Acyclic domination number
  • Diameter two

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Cite this