On the maximum number of maximum independent sets of bipartite graphs

Abstract An independent set in a graph G is a set of pairwise non-adjacent vertices of G. The independence number, α, of G is the maximum cardinality of an independent set in G. An independent set in G is maximum if it has cardinality α. Mohr and Rautenbach determined the n-vertex trees (resp. disconnected graphs) with independence number α having the largest number of maximum independent sets. Quite recently, Mohr and Rautenbach characterized the connected graphs of order n and independence number α that maximize the number of maximum independent sets. As a continuance of these works, we characterize the bipartite graphs (containing at least one cycle) of order n and independence number α having the maximum number of maximum independent sets. Furthermore, we determine the n-vertex trees with independence number α having the second and third largest number of maximum independent sets. We also characterize the n-vertex forests with independence number α having the first three largest number of maximum independent sets. Among the n-vertex disconnected graphs with independence number α we identify the graphs with the second largest number of maximum independent sets. Our result gives a solution to an open problem of Derikvand and Oboudi [4], and we obtain a complete classification of connected graphs with order n and independence number n − 3. AMS subject classification: 05C69, 05C35