Total domination critical and stable graphs upon edge removal (Q602674)

A set of vertices in a graph \(G\) ia a total dominating set, in short \(TDS\), of \(G\) if every vertex of \(G\) is adjacent to some vertex in \(S\). The minimum cardinality of a \(TDS\) is the total domination number \(\gamma_t(G)\) of \(G\). A \(TDS\) of \(G\) of cardinality \(\gamma_t(G)\) is called a \(\gamma_t\)-set. A graph \(G\) is total domination edge critical or \(\gamma_t\)-critical if the removal of any arbitrary edge increases the total domination number. In this paper the authors prove that a graph \(G\) is a \(\gamma_t\)-critical graph if and only if it is a non-trivial star, or a double star or can be obtained from a subdivided star \(K_{1,k}^*\), where \(k \geq 2\), by adding zero or more pendant edges to the non-leaf vertices of \(K_{1,k}^*\). A graph is total domination edge stable or \(\gamma_t\)-stable if the removal of any arbitrary edge has no effect on the total domination number. The authors investigate several properties of \(\gamma_t\)-stable graphs such as if \(G\) is \(\gamma_t\)-stable then \(\delta(G) \geq 2\) and \(G\) has at least two distinct \(\gamma_t\)-sets. They also prove that there is no forbidden subgraph characterization for \(\gamma_t\)-stable graphs. They also characterize bipartite \(\gamma_t\)-stable graphs. For a connected graph \(G\), they establish the relation \(\mathrm{diam}(G) \leq \gamma_t(G) + 2c(G) - 1\), where \(c(G)\) is the minimum number of components in the subgraph induced by a \(\gamma_t\)-set and obtain infinite families of graphs which satisfy equality in the above relation.