An upper bound for the number of independent sets in regular graphs

DOI10.1016/j.disc.2009.06.031zbMath1236.05111arXiv1007.4811OpenAlexW2108149667MaRDI QIDQ1045204

David Galvin

Publication date: 15 December 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

stable setindependent sethard-core model

Mathematics Subject Classification ID

Graph polynomials (05C31) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (7)

On the number of connected sets in bounded degree graphs ⋮ Counting maximal antichains and independent sets ⋮ Counting independent sets in triangle-free graphs ⋮ On the Number of Connected Sets in Bounded Degree Graphs ⋮ On the average size of independent sets in triangle-free graphs ⋮ Two problems on independent sets in graphs ⋮ Counting colorings of a regular graph

Cites Work

• Unnamed Item
• Unnamed Item
• Matchings and independent sets of a fixed size in regular graphs
• Independent sets in regular graphs and sum-free subsets of finite groups
• An Entropy Approach to the Hard-Core Model on Bipartite Graphs
• On weighted graph homomorphisms
• Information Inequalities for Joint Distributions, With Interpretations and Applications
• An upper bound for the number of maximal independent sets in a graph

This page was built for publication: An upper bound for the number of independent sets in regular graphs