On the maximum number of maximum independent sets in connected graphs

Abstract

We characterize the connected graphs of given order $n$ and given independence number $\alpha$ that maximize the number of maximum independent sets. For $3\le \alpha \le n/2$, there is a unique such graph that arises from the disjoint union of $\alpha$ cliques of orders $\lceil \frac{n}{\alpha }\rceil$ and $\lfloor \frac{n}{\alpha }\rfloor$, by selecting a vertex $x$ in a largest clique and adding an edge between $x$ and a vertex in each of the remaining $\alpha -1$ cliques. Our result confirms a conjecture of Derikvand and Oboudi [On the number of maximum independent sets of graphs, Transactions on Combinatorics 3 (2014) 29-36].