## 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. 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 language | English |
---|---|

Pages (from-to) | 613-626 |

Number of pages | 14 |

Journal | Discussiones Mathematicae - Graph Theory |

Volume | 42 |

Issue number | 2 |

DOIs | |

Publication status | Published - 1 May 2022 |

## Keywords

- cactus graphs
- cycles
- domination number
- lower bounds

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics