On The Product Of \(k\)-Minimal Domination Numbers of a Graph and Its Complement

The \({domination \; number}\) \(\gamma(G)\) of a graph \(G = (V, E)\) is the smallest cardinality of a \({dominating}\) set \(X\) of \(G\), i.e., of a subset \(X\) of vertices such that each \(v \in V – X\) is adjacent to at least one vertex of \(X\). The \(k\)-\({minimal \; domination \; number}\) \(\Gamma_k(G)\) is the largest cardinality of a dominating set \(Y\) which has the following additional property: For every \(\ell\)-subset \(Z\) of \(Y\) where \(\ell \leq k\), and each \((\ell-1)\)-subset \(W\) of \(V – Y\), the set \((Y – Z) \cup W\) is not dominating. In this paper, for any positive integer \(k \geq 2\), we exhibit self-complementary graphs \(G\) with \(\gamma(G) > k\) and use this and a method of Graham and Spencer to construct \(n\)-vertex graphs \(F\) for which \(\Gamma_k(F)\Gamma_k(\overline{F})>n\).