Counting independent sets in regular graphs with bounded independence number

David Galvin, Phillip Marmorino

An $n$-vertex, $d$-regular graph can have at most $2^{n/2+o_d(n)}$ independent sets. In this paper we address what happens with this upper bound when we impose the further conditio…