A new lower bound on the double domination number of a graph

Majid Hajian | Nader Jafari Rad

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=106243
Date :  2019/02/08
Publish in :    Discrete Applied Mathematics
DOI :  https://doi.org/10.1016/j.dam.2018.06.009
Link :  http://dx.doi.org/https://doi.org/10.1016/j.dam.2018.06.009
Keywords :bound, double, graph

Abstract :

---

A subset S of vertices of a graph G is a double dominating set of G if every vertex in V(G)−S has at least two neighbors in S and every vertex of S has a neighbor in S. The double domination number γ×2(G) is the minimum cardinality of a double dominating set of G. Chellali (2006) showed that if T is a nontrivial tree of order n, with ℓ leaves and s support vertices, then γ×2(T ) ≥ (2n + ℓ − s + 2)/3. In this paper we generalize the above lower bound for any connected graph. We show that if G is a connected graph of order n ≥ 2 with k ≥ 0 cycles, ℓ leaves and s support vertices, then γ×2(G) ≥ (2n+ℓ−s+2)/3−2k/3. We also characterize all graphs achieving equality for this new bound.