On the Number of k‐Dominating Independent Sets |
| |
| Authors: | Zoltán Lóránt Nagy |
| |
| Affiliation: | MTA‐ELTE GEOMETRIC AND ALGEBRAIC COMBINATORICS RESEARCH GROUP, HUNGARY |
| |
| Abstract: | We study the existence and the number of k‐dominating independent sets in certain graph families. While the case  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  and  if  , moreover the maximum number of 2‐dominating independent sets in n‐vertex graphs is between  and  . Graph constructions containing a large number of k‐dominating independent sets are coming from product graphs, complete bipartite graphs, and finite geometries. The product graph construction is associated with the number of certain Maximum Distance Separable (MDS) codes. |
| |
| Keywords: | k‐DIS domination maximal independent sets k‐dominating MDS codes finite geometry hyperoval ‐arcs |
|
|
