An improvement on the maximum number of $k$-Dominating Independent Sets

Abstract

Erdős and Moser raised the question of determining the maximum number of maximal cliques or equivalently, the maximum number of maximal independent sets in a graph on $n$ vertices. Since then there has been a lot of research along these lines. A $k$-dominating independent set is an independent set $D$ such that every vertex not contained in $D$ has at least $k$ neighbours in $D$. Let $m{i}_k(n)$ denote the maximum number of $k$-dominating independent sets in a graph on $n$ vertices, and let ${\zeta }_k:={\lim }_{n\to \infty }\sqrt[n]{m{i}_k(n)}$. Nagy initiated the study of $m{i}_k(n)$. In this article we disprove a conjecture of Nagy and prove that for any even $k$ we have $$1.489\approx \sqrt[9]{36}\le {\zeta }_k^k.$$ We also prove that for any $k\ge 3$ we have $${\zeta }_k^k\le 2.053^{\frac{1}{1.053+1/k}}<1.98,$$ improving the upper bound of Nagy.

11 pages