A new lower bound on the domination number of a graph

Majid Hajian | Michael A. Henning | Nader Jafari Rad

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=116511
Date :  2019/05/04
Publish in :    Journal of Combinatorial Optimization
DOI :  https://doi.org/10.1007/s10878-019-00409-x
Link :  https://link.springer.com/article/10.1007/s10878-019-00409-x
Keywords :,dominating set,bound, graph

Abstract :

---

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−2k)/3⌉. We also characterize the graphs G achieving equality for this new bound.