Domination and Total Domination Critical Trees with Respect to Relative Complements

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}\). For a graphical parameter \(\mu(G)\), a graph \(G\) is \(\mu(G)\)-critical if \(\mu(G + e) < \mu(G)\) for every \(e\) in the ordinary complement \(\bar{G}\) of \(G\), while \(G\) is \(\mu(G)\)-critical relative to \(K_{s,s}\) if \(\mu(G + e) < \mu(G)\) for all \(e \in E(H)\). We show that no tree \(T\) is \(\mu(T)\)-critical and characterize the trees \(T\) that are \(\mu(T)\)-critical relative to \(K_{s,s}\), where \(\mu(T)\) is the domination number and the total domination number of \(T\).