@article{167da72bedb047b5b7a5105700d24ab5,
title = "An improvement on the maximum number of k-dominating independent sets",
abstract = "Erd{\H o}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.",
keywords = "almost twin vertices, independent sets, k-dominating sets",
author = "D{\'a}niel Gerbner and Bal{\'a}zs Keszegh and Abhishek Methuku and Bal{\'a}zs Patk{\'o}s and M{\'a}t{\'e} Vizer",
note = "We thank the anonymous reviewers for their careful reading of our manuscript and their many insightful comments and suggestions improving the presentation of our article. We are also grateful to the MTA Resort Center of Balatonalm{\'a}di for their hospitality, where this study was initiated during the Workshop on Graph and Hypergraph Domination in June 2017. We thank D{\'a}niel Solt{\'e}sz for helping us in the optimization process, and for introducing us to Wolframalpha cloud (https://www.wolframcloud.com/). Research of Gerbner and Patk{\'o}s was supported by the J{\'a}nos Bolyai Research Fellowship of the Hungarian Academy of Sciences. Research of Gerbner, Keszegh, Methuku, and Patk{\'o}s was supported by the National Research, Development and Innovation Office—NKFIH, grant K 116769. Research of Patk{\'o}s and Vizer was supported by the National Research, Development and Innovation Office—NKFIH, grant SNN 116095. Research of Gerbner, Patk{\'o}s and Vizer was supported by the National Research, Development and Innovation Office-NKFIH, grant SNN 129364. Research of Gerbner and Vizer was supported by the National Research, Development and Innovation Office—NKFIH, grant KH 130371. Research of Keszegh was supported by the by the Lend\textbackslash{}{"}ulet program of the Hungarian Academy of Sciences (MTA), grant LP2017-19/2017. We thank the anonymous reviewers for their careful reading of our manuscript and their many insightful comments and suggestions improving the presentation of our article. We are also grateful to the MTA Resort Center of Balatonalm{\'a}di for their hospitality, where this study was initiated during the Workshop on Graph and Hypergraph Domination in June 2017. We thank D{\'a}niel Solt{\'e}sz for helping us in the optimization process, and for introducing us to Wolframalpha cloud (https://www. wolframcloud.com/). Research of Gerbner and Patk{\'o}s was supported by the J{\'a}nos Bolyai Research Fellowship of the Hungarian Academy of Sciences. Research of Gerbner, Keszegh, Methuku, and Patk{\'o}s was supported by the National Research, Development and Innovation Office—NKFIH, grant K 116769. Research of Patk{\'o}s and Vizer was supported by the National Research, Development and Innovation Office—NKFIH, grant SNN 116095. Research of Gerbner, Patk{\'o}s and Vizer was supported by the National Research, Development and Innovation Office—NKFIH, grant SNN 129364. Research of Gerbner and Vizer was supported by the National Research, Development and Innovation Office— NKFIH, grant KH 130371. Research of Keszegh was supported by the by the Lend\textbackslash{}{"}ulet program of the Hungarian Academy of Sciences (MTA), grant LP2017-19/2017.",
year = "2019",
month = may,
doi = "10.1002/jgt.22422",
language = "English (US)",
volume = "91",
pages = "88--97",
journal = "Journal of Graph Theory",
issn = "0364-9024",
publisher = "Wiley-Liss Inc.",
number = "1",
}