On The Product Of $k$-Minimal Domination Numbers of a Graph and Its Complement

Abstract

The $dominationnumber$ $\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$-$minimaldominationnumber$ ${\mathrm{\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 \le 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\ge 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 ${\mathrm{\Gamma }}_k(F){\mathrm{\Gamma }}_k(\overline{F})>n$.