A Classification of Cactus Graphs According to their Domination Number

Majid Hajian, Michael A. Henning, Nader Jafari Rad

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


A set S of vertices in a graph G is a dominating set of G if every vertex not in S is adjacent to some vertex in S. The domination number, γ(G), of G is the minimum cardinality of a dominating set of G. The authors proved in [A new lower bound on the domination number of a graph, J. Comb. Optim. 38 (2019) 721-738] that if G is a connected graph of order n ≥ 2 with k ≥ 0 cycles and l leaves, then γ(G) ≥ ?(n - l + 2 - 2k)/3?. As a consequence of the above bound, γ(G) = (n - l + 2(1 - k) + m)/3 for some integer m ≥ 0. In this paper, we characterize the class of cactus graphs achieving equality here, thereby providing a classification of all cactus graphs according to their domination number.

Original languageEnglish
Pages (from-to)613-626
Number of pages14
JournalDiscussiones Mathematicae - Graph Theory
Issue number2
Publication statusPublished - 1 May 2022


  • cactus graphs
  • cycles
  • domination number
  • lower bounds

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'A Classification of Cactus Graphs According to their Domination Number'. Together they form a unique fingerprint.

Cite this