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

DOI10.1002/JGT.22422MaRDI QIDQ5379840zbMATHOpenAlexWikidataFDO

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

Publication date 14 June 2019

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.04720

zbMATH Keywords

independent sets\(k\)-dominating setsalmost twin vertices

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30) Structural characterization of families of graphs (05C75)

Abstract: ErdH{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$ neighbours in $D$. Let $m{i}_k(n)$ denote the maximum number of $k$-dominating independent sets in a graph on $n$ vertices, and let $zet{a}_k:=li{m}_{nightarrowinfty}sqrt[n]m{i}_k(n)$. Nagy initiated the study of $m{i}_k(n)$. In this article we disprove a conjecture of Nagy and prove that for any even $k$ we have ${\displaystyle }$1.489 approx sqrt[9]{36} le zeta^k_k.${\displaystyle }$ We also prove that for any $kge3$ we have ${\displaystyle }$zeta_k^{k} le 2.053^{frac{1}{1.053+1/k}}< 1.98,${\displaystyle }$ improving the upper bound of Nagy.

Recommendations

• Generalizing Erdős, Moon and Moser's result -- the number of \(k\)-dominating independent sets
• On the number of \(k\)-dominating independent sets
• On Dominating Sets and Independent Sets of Graphs
• scientific article; zbMATH DE number 1389216
• Independence and \(k\)-domination in graphs

Cited in

(7)

• Further Improvement on Maximum Independent Set in Degree-4 Graphs
• scientific article; zbMATH DE number 1389216 (Why is no real title available?)
• On the number of \(k\)-dominating independent sets
• On the number of \(k\)-dominating independent sets in planar graphs
• scientific article; zbMATH DE number 792644 (Why is no real title available?)
• Generalizing Erdős, Moon and Moser's result -- the number of \(k\)-dominating independent sets
• Improved lower bounds on k‐independence

This page was built for publication: An improvement on the maximum number of \(k\)-dominating independent sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5379840)