A new lower bound on the domination number of a graph

Majid Hajian, Michael A. Henning, Nader Jafari Rad

Research output: Contribution to journalArticlepeer-review

10 Citations (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. Lemańska (Discuss Math Graph Theory 24:165–170, 2004) showed that if T is a tree of order n≥ 2 with ℓ leaves, then γ(T) ≥ (n- ℓ+ 2) / 3 , and characterized all trees achieving equality in this bound. In this paper, we first characterize all trees T of order n with ℓ leaves satisfying γ(T) = ⌈ (n- ℓ+ 2) / 3 ⌉. We then generalize this result to connected graphs and show that if G is a connected graph of order n≥ 2 with k≥ 0 cycles and ℓ leaves, then γ(G) ≥ ⌈ (n- ℓ+ 2 - 2 k) / 3 ⌉. We also characterize the graphs G achieving equality for this new bound.

Original languageEnglish
Pages (from-to)721-738
Number of pages18
JournalJournal of Combinatorial Optimization
Issue number3
Publication statusPublished - 15 Oct 2019


  • Cycles
  • Domination number
  • Lower bounds

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'A new lower bound on the domination number of a graph'. Together they form a unique fingerprint.

Cite this