Premium
An improvement on the maximum number of k ‐dominating independent sets
Author(s) -
Gerbner Dániel,
Keszegh Balázs,
Methuku Abhishek,
Patkós Balázs,
Vizer Máté
Publication year - 2019
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22422
Subject(s) - combinatorics , mathematics , conjecture , vertex (graph theory) , dominating set , independent set , graph , upper and lower bounds , maximal independent set , discrete mathematics , line graph , pathwidth , mathematical analysis
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.