Maximizing the number of independent sets of fixed size in connected graphs with given independence number (Q1684927)

The authors study the problem of determining the maximum number of independent sets of fixed cardinality in a connected graph of fixed order and fixed independence number. Generalizing an earlier result due to \textit{V. Bruyère} and \textit{H. Mélot} [J. Comb. Optim. 18, No. 3, 207--228 (2009; Zbl 1203.05074)], the authors show that for every choice of positive integers \(\beta \leq \alpha\leq n\), the Turán-connected graph \(\text{TC}_{n\alpha}\) maximizes the number of independent sets of size \(\beta\) among all connected \(n\)-vertex graphs with independence number \(\alpha\). The Turán-connected graph \(\text{TC}_{n\alpha}\) is the graph obtained from the disjoint union of \(\alpha\) complete graphs whose orders sum up to \(n\) and are as equal as possible by adding \(\alpha-1\) additional edges going out from one vertex in one of the complete graphs of order \(\left\lceil \frac{n}{\alpha}\right\rceil\) to make the graph connected. Their approach also leads to new proofs of: 1) a result obtained by \textit{M.-J. Jou} and \textit{G. J. Chang} [Taiwanese J. Math. 4, No. 4, 685--695 (2000; Zbl 0967.05038)] determining the largest possible number of maximum independent sets in a connected graph of fixed order and characterizing the extremal graphs, and 2) characterizations of \(n\)-vertex trees with the largest possible number of independent sets or maximum independent sets, obtained by \textit{H. Prodinger} and \textit{R. F. Tichy} [Fibonacci Q. 20, 16--21 (1982; Zbl 0475.05046)] and \textit{J. Zito} [J. Graph Theory 15, No. 2, 207--221 (1991; Zbl 0764.05082)], respectively. The paper is well written, with proofs involving a combination of case analysis, graph structural arguments (including some classical graph theory results such as Brooks' theorem), induction, and counting arguments.