On the number of k-dominating independent sets

We study the existence and the number of k-dominating independent sets in certain graph families. While the case $k=1$ namely the case of maximal independent sets - which is originated from Erdős and Moser - is widely investigated, much less is known in general. In this paper we settle the question for trees and prove that the maximum number of k-dominating independent sets in n-vertex graphs is between cₖ·√[2k]2ⁿ and cₖ'·√[k+1]2ⁿ if k≥ 2, moreover the maximum number of $2$-dominating independent sets in n-vertex graphs is between c· 1.22ⁿ and c'·1.246ⁿ. Graph constructions containing a large number of k-dominating independent sets are coming from product graphs, complete bipartite graphs and with finite geometries. The product graph construction is associated with the number of certain MDS codes.