A CLASSIFICATION OF CACTUS GRAPHS ACCORDING TO THEIR DOMINATION NUMBER

Hajian | Michael A. Henning | Nader Jafari Rad

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=137638
Date :  2020/11/26
Publish in :    Discussiones Mathematicae Graph Theory

Link :  https://www.dmgt.uz.zgora.pl/publish/inpress.php
Keywords :domination number, lower bounds, cycles, cactus graphs

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) 721738 that if G is a connected graph of order n  2 with k  0 cycles and leaves, then (G)  d(n 􀀀 + 2 􀀀 2k)=3e. As a consequence of the above bound, (G) = (n 􀀀 + 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 classication of all cactus graphs according to their domination number.