An improvement on the maximum number of k-dominating independent sets

Erdos 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 neighbors in D. Let mi(k) (n) denote the maximum number of k-dominating independent sets in a graph on n vertices, and let zeta(k) := lim(n ->infinity)(n)root mi(k)(n). Nagy initiated the study of mi(k)(n). In this study, we disprove a conjecture of Nagy using a graph product construction and prove that for any even k we have 1.489 approximate to 9 root 36 <= zeta(k)(k). We also prove that for any k >= 3 we have zeta(k)((1/(1.053+1/k)))(k)( <= 2.053)( < 1.98,) improving the upper bound of Nagy.