Relating the total domination number and the annihilation number of cactus graphs and block graphs - Bujtás, Csilla (Ars mathematica contemporanea, 2019)
The total domination number ?$γ_t(G)$? of a graph ?$G$? is the order of a smallest set ?$D \subseteq V(G)$? such that each vertex of ?$G$? is adjacent to some vertex in ?$D$?. The annihilation number ?$a(G)$? of ?$G$? is the largest integer ?$k$? such that there exist ?$k$? different vertices in ?$G$? with degree sum of at most ?$|E(G)|$?. It is conjectured that ?$γ_t(G) ≤ a(G) + 1$? holds for every nontrivial connected graph ?$G$?. The conjecture was proved for graphs with minimum degree at least 3, and remains unresolved for graphs with minimum degree 1 or 2. In this paper we establish the conjecture for cactus graphs and block graphs.
Keywords: annihilation number; block graph; bločni graf; cactus graph; indeks popolne prevlade; indeks uničenja; kaktusni graf; total domination number