The number of independent sets in an irregular graph
Settling Kahn's conjecture (2001), we prove the following upper bound on the number i(G) of independent sets in a graph G without isolated vertices: i(G)≤∏uv∈E(G)i(Kdu,dv)1/(dudv), where du is the degree of vertex u in G. Equality occurs when G is a disjoint union of complete bipartite graphs....
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Elsevier BV
2020
|
| Online Access: | https://hdl.handle.net/1721.1/126178 |