Shahed University
A Classification of Cactus Graphs According to Their Total Domination Number
Majid Hajian | Michael A. Henning | Nader Jafari Rad
URL :
http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=106435
Date :
2019/04/08
Publish in :
Bulletin of the Malaysian Mathematical Sciences Society
DOI :
https://doi.org/10.1007/s40840-019-00758-0
Link :
https://link.springer.com/article/10.1007/s40840-019-00758-0
Keywords :
Cactus, Graphs, According, Domination, Number
Abstract :
A set S of vertices in a graph G is a total dominating set of G if every vertex in G is adjacent to some vertex in S. The total domination number, γt(G), is the minimum cardinality of a total dominating set of G. A cactus is a connected graph in which every edge belongs to at most one cycle. Equivalently, a cactus is a connected graph in which every block is an edge or a cycle. Let G be a connected graph of order n≥2 with k≥0 cycles and ℓ leaves. Recently, the authors have proved that γt(G)≥12(n−ℓ+2)−k. As a consequence of this bound, γt(G)=12(n−ℓ+2+m)−k for some integer m≥0. In this paper, we characterize the class of cactus graphs achieving equality in this bound, thereby providing a classification of all cactus graphs according to their total domination number.
Files in this item :
Download
Name :
106435_11825567110.pdf
Size :
383Kb
Format :
PDF
Authors' Home page
Nader Jafari Rad