The Number of Independent Sets in a Graph with Small Maximum Degree |
| |
| Authors: | David Galvin Yufei Zhao |
| |
| Institution: | 1. Department of Mathematics, University of Notre Dame, 255 Hurley Hall, Notre Dame, IN, 46556, USA
2. Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, 02139, USA
|
| |
| Abstract: | 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(Kd(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)}} |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
|
