On the maximum number of maximum independent sets

Abstract

We give a very short and simple proof of Zykov's generalization of Turán's theorem, which implies that the number of maximum independent sets of a graph of order $n$ and independence number $\alpha$ with $\alpha <n$ is at most ${\lceil \frac{n}{\alpha }\rceil }^{n\mathrm{mod}\alpha }{\lfloor \frac{n}{\alpha }\rfloor }^{\alpha -(n\mathrm{mod}\alpha )}$. Generalizing a result of Zito, we show that the number of maximum independent sets of a tree of order $n$ and independence number $\alpha$ is at most $2^{n-\alpha -1}+1$, if $2\alpha =n$, and, $2^{n-\alpha -1}$, if $2\alpha >n$, and we also characterize the extremal graphs. Finally, we show that the number of maximum independent sets of a subcubic tree of order $n$ and independence number $\alpha$ is at most ${\left(\frac{1+\sqrt{5}}{2}\right)}^{2n-3\alpha +1}$, and we provide more precise results for extremal values of $\alpha$.