Total Domination Critical Graphs with Respect to Relative Complements

Abstract

A set \(S\) of vertices of a graph \(G\) is a total dominating set if every vertex of \(V(G)\) is adjacent to some vertex in \(S\). The total domination number \(\gamma_t(G)\) is the minimum cardinality of a total dominating set of \(G\). Let \(G\) be a spanning subgraph of \(K_{s,s}\), and let \(H\) be the complement of \(G\) relative to \(K_{s,s}\); that is, \(K_{s,s} = G \oplus H\) is a factorization of \(K_{s,s}\). The graph \(G\) is \(k\)-critical relative to \(K_{s,s}\) if \(\gamma_t(G) = k\) and \(\gamma_t(G + e) < k\) for all \(e \in E(H)\). We study \(k_t\)-critical graphs relative to \(K_{s,s}\) for small values of \(k\). In particular, we characterize the \(3\)-critical and \(4_t\)-critical graphs.