An improvement on the maximum number of k-dominating independent sets

Dániel Gerbner, Balázs Keszegh, Abhishek Methuku, Balázs Patkós, Máté Vizer

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)88-97
Number of pages10
JournalJournal of Graph Theory
Volume91
Issue number1
DOIs
StatePublished - May 2019
Externally publishedYes

Keywords

  • almost twin vertices
  • independent sets
  • k-dominating sets

ASJC Scopus subject areas

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'An improvement on the maximum number of k-dominating independent sets'. Together they form a unique fingerprint.

Cite this