The number of independent sets in a graph with small maximum degree

DOI10.1007/S00373-010-0976-ZzbMATH Open1235.05104arXiv1007.4803OpenAlexW2111038853MaRDI QIDQ659691FDOQ659691

David Galvin, Yufei Zhao

Publication date: 24 January 2012

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: Let $mind(G)$ be the number of independent sets in a graph $G$. We show that if $G$ has maximum degree at most $5$ then ${\displaystyle }$ { m ind}(G) leq 2^{{ m iso}(G)} prod_{uv in E(G)} { m ind}(K_{d(u),d(v)})^{frac{1}{d(u)d(v)}} ${\displaystyle }$ (where $d(cdot)$ is vertex degree, $miso(G)$ is the number of isolated vertices in $G$ and $K_{a,b}$ is the complete bipartite graph with $a$ vertices in one partition class and $b$ in the other), with equality if and only if each connected component of $G$ is either a complete bipartite graph or a single vertex. This bound (for all $G$) was conjectured by Kahn. A corollary of our result is that if $G$ is $d$-regular with $1leqdleq5$ then ${\displaystyle }$ { m ind}(G) leq left(2^{d+1}-1 ight)^frac{|V(G)|}{2d}, ${\displaystyle }$ with equality if and only if $G$ is a disjoint union of $V(G)/2d$ copies of $K_{d,d}$. This bound (for all $d$) was conjectured by Alon and Kahn and recently proved for all $d$ by the second author, without the characterization of the extreme cases. Our proof involves a reduction to a finite search. For graphs with maximum degree at most $3$ the search could be done by hand, but for the case of maximum degree $4$ or $5$, a computer is needed.

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

zbMATH Keywords

Independent setRegular graphStable set

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30)

Cites Work

• An entropy approach to the hard-core model on bipartite graphs
• The Number of Independent Sets in a Regular Graph
• Independent sets in regular graphs and sum-free subsets of finite groups

Cited In (9)

• The number of independent sets in an irregular graph
• Independent sets in graphs
• Independent sets in graphs with given minimum degree
• Extremal Regular Graphs: Independent Sets and Graph Homomorphisms
• Extremal H‐Colorings of Graphs with Fixed Minimum Degree
• Counting MSTD sets in finite abelian groups
• A reverse Sidorenko inequality
• On graphs with maximal independent sets of few sizes, minimum degree at least 2, and girth at least 7
• Hölder-type inequalities and their applications to concentration and correlation bounds

This page was built for publication: The number of independent sets in a graph with small maximum degree

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