A new lower bound on the total domination number of a graph. Issue 1 (2nd January 2023)

• Record Type: Journal Article
• Authors: Hajian, Majid; Henning, Michael A.; Rad, Nader Jafari
• Is Part Of: Quaestiones mathematicae. Volume 46:Issue 1(2023)
• Page Start: 35
• Page End: 48
• Publication Date: 2023-01-02
• Subjects: 05C69; Total domination -- lower bounds -- cycles; Mathematics -- Periodicals; 510.5
• DOI: 10.2989/16073606.2021.1988002
• Languages: English
• ISSNs: 1607-3606

Abstract

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 . Chellali and Haynes [ J. Combin. Math. Combin. Comput. 58 (2006), 189–193] showed that if T is a nontrivial tree of order n, with ℓ leaves, then γt ( T ) ≥ ( n − ℓ + 2) / 2. In this paper, we first characterize all trees T of order n with ℓ leaves satisfying γt ( T ) = ⌈( n − ℓ +2) / 2⌉. 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 γt ( G ) ≥ ⌈( n − ℓ + 2) / 2⌉ − k . We also characterize the graphs G achieving equality for this new bound.