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.