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

DOI10.1002/JGT.22422zbMATH Open1414.05225arXiv1709.04720OpenAlexW2963221276WikidataQ128844812 ScholiaQ128844812MaRDI QIDQ5379840FDOQ5379840

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)

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.

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

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

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)

Cited In (5)

• Title not available (Why is that?)
• Further Improvement on Maximum Independent Set in Degree-4 Graphs
• Title not available (Why is that?)
• On the number of \(k\)-dominating independent sets in planar graphs
• 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)