The Number of Independent Sets in a Graph with Small Maximum Degree

摘要

Let ind(G) be the number of independent sets in a graph G. We show that if G has maximum degree at most 5 then ind(G) £ 2iso(G) Õ_{uv Î E(G)} ind(K_d(u),d(v))frac1d(u)d(v){rm ind}(G) leq 2^{{rm iso}(G)} prod_{uv in E(G)} {rm ind}(K_{d(u),d(v)})^{frac{1}{d(u)d(v)}}