Abstract:
The study of the number of independent sets in a graph has a rich history. Recently, Kahn proved that disjoint unions of \(K_{r,r}\)'s have the maximum number of independent sets amongst \(r\)-regular bipartite graphs. Zhao extended this to all \(r\)-regular graphs. I'll discuss some related questions concerning the maximization and minimization of the number of independent sets in a graph under a variety of conditions.