Relating the total domination number and the annihilation number for quasi-trees and some composite graphs (Q2144511)

Let \(G = (V(G), E(G))\) be a simple graph. A subset \(D\) of \(V(G)\) is called a total dominating set of \(G\) if every vertex of \(G\) is adjacent to at least one vertex in \(D\). The total domination number of \(G\), denoted by \(\gamma_{t}(G)\), is defined to be the minimum cardinality of a total dominating set of \(G\). The annihilation number of \(G\), denoted by \(a(G)\), is the largest integer \(k\) such that there are \(k\) distinct vertices of \(G\) whose degree sum is at most \(|E(G)|\). It was conjectured that \(\gamma_{t}(G) \leq a(G) + 1\) holds for any non-trivial connected graph \(G\). In the literature, this conjecture has been proved for graphs with a minimum degree of at least 3, trees, certain tree-like graphs, block graphs, and cactus graphs. In this paper, the authors prove that this conjecture is also true for all non-trivial quasi-trees, where a graph \(G\) is called a quasi-tree if there exists a vertex \(x \in V(G)\) such that \(G - x\) is a tree, and a quasi-tree is non-trivial if it is not a tree. They also verify this conjecture for some graph constructions, including bijection graphs, Mycielskians, and universally-identifying graphs, the last being introduced in this paper.