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 neighbors in D. Let mik(n) denote the maximum number of k-dominating independent sets in a graph on n vertices, and let ζk ≔ limn→∞n√mik(n). Nagy initiated the study of mik(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 ≈ 9√36 ≤ ζkk. We also prove that for any k ≥ 3 we have. ζkk ≤ 2.053(1/(1.053+1/k)) < 1.98, improving the upper bound of Nagy.
Original language | English (US) |
---|---|
Pages (from-to) | 88-97 |
Number of pages | 10 |
Journal | Journal of Graph Theory |
Volume | 91 |
Issue number | 1 |
DOIs | |
State | Published - May 2019 |
Externally published | Yes |
Keywords
- almost twin vertices
- independent sets
- k-dominating sets
ASJC Scopus subject areas
- Geometry and Topology
- Discrete Mathematics and Combinatorics