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

Original language | English |
---|---|

Pages (from-to) | 721-738 |

Number of pages | 18 |

Journal | Journal of Combinatorial Optimization |

Volume | 38 |

Issue number | 3 |

DOIs | |

Publication status | Published - 15 Oct 2019 |

## Keywords

- 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