Counting independent sets in cubic graphs of given girth

Guillem Perarnau, Will Perkins

We prove a tight upper bound on the independence polynomial (and total number of independent sets) of cubic graphs of girth at least 5. The bound is achieved by unions of the Heawo…