Total domination supercritical graphs with respect to relative complements (Q1850074)

The authors define a graph \(G\) to be total domination \(k\)-supercritical relative to \(K_{s,s}\), if \(G\) is a connected spanning subgraph of \(K_{s,s}\) and \(\gamma_t(G+e)=\gamma_t(G)-2=k-2\) for every edge \(e\in E(K_{s,s})\setminus E(G)\) where \(\gamma_t\) denotes the total domination number. After proving some basic properties of such graphs related to vertex degrees, neighbourhoods and the diameter, the authors prove the existence of such graphs for every even \(k\geq 4\) and diameters \(k=1\) and \(5\). They characterize total domination \(k\)-supercritical graphs relative to \(K_{s,s}\) for \(k=4\), \(k=6\) and diameter \(4\) and \(k=6\) and diameter \(5\). The paper closes with a series of open problems.