2018/06/27 by Mohr, E., Rautenbach, D.
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1806.10424
We characterize the connected graphs of given order n and given independence number α that maximize the number of maximum independent sets. For 3≤ α≤ n/2, there is a unique such graph that arises from the disjoint union of α cliques of orders \lceil\fracnα\rceil and \lfloor\fracnα\rfloor, by selecting a vertex x in a largest clique and adding an edge between x and a vertex in each of the remaining α-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].