On the maximum number of maximum independent sets in connected graphs
Elena Mohr, Dieter Rautenbach · Journal of Graph Theory · 2020
Abstract We characterize the connected graphs of given order and given independence number that maximize the number of maximum independent sets. For , there is a unique such graph that arises from the disjoint union of cliques of orders and , which is the complement of a Turán graph, by selecting a vertex in a largest clique and adding an edge between and a vertex in each of the remaining cliques. Our result confirms a conjecture of Derikvand and Oboudi.