Maximizing the number of independent sets of fixed size in connected graphs with given independence number
type: Item
instance of: scholarly article
title: Maximizing the number of independent sets of fixed size in connected graphs with given independence number
zbMATH Open document ID: 1395.05129
author: Peng Zhang
published in: Graphs and Combinatorics
publication date: 2017-12-12T00:00:00Z
review text: 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.
reviewed by: Martin Milanič
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 6817803
zbMATH Keywords: independent set
zbMATH Keywords: independence number
zbMATH Keywords: connected graph
zbMATH Keywords: Turán connected graph
zbMATH Keywords: extremal graph theory
MaRDI profile type: Publication
full work available at URL: s00373-017-1825-0
OpenAlex ID: W2727726954
cites work: Q3852212
cites work: Turán's theorem and k‐connected graphs
cites work: Q5782525
cites work: Trees with given stability number and minimum number of stable sets
cites work: Fibonacci index and stability number of graphs: a polyhedral study
cites work: Q5724802
cites work: On the number of complete subgraphs and circuits contained in graphs
cites work: The number of maximal independent sets in connected graphs
cites work: The number of maximal independent sets in a connected graph
cites work: Another extremal problem for Turan graphs
cites work: The number of maximum independent sets in graphs
cites work: Q4276003
cites work: Q3931424
cites work: The maximum number of q-cliques in a graph with no p-clique
cites work: Maximal and maximum independent sets in graphs with at mostr cycles
cites work: A generalization of a theorem of Turán
cites work: Maxima and minima of the Hosoya index and the Merrifield-Simmons index
cites work: The structure and maximum number of maximum independent sets in trees
DOI: 10.1007/S00373-017-1825-0
description: scientific article; zbMATH DE number 6817803