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

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 neighbors in D . Let m i k ( n ) denote the maximum number of k ‐dominating independent sets in a graph on n vertices, and let ζ k ≔ lim n → ∞m i k ( n ) n . Nagy initiated the study of m i k ( n ) . In this study, we disprove a conjecture of Nagy using a graph product construction and prove that for any even k we have1.489 ≈ 36 9 ≤ ζ k k .We also prove that for any k ≥ 3 we haveζ k k ≤ 2.05 3 ( 1 / ( 1.053 + 1 ∕ k ) ) < 1.98 ,improving the upper bound of Nagy.