The structure and maximum number of maximum independent sets in trees

DOI10.1002/jgt.3190150208zbMath0764.05082OpenAlexW2121767044MaRDI QIDQ3978364

Jennifer S. Zito

Publication date: 25 June 1992

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.3190150208

zbMATH Keywords

treemaximum independent set\(\alpha\)-critical edges

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75)

Related Items

Maximal and maximum dissociation sets in general and triangle-free graphs, Combinatorial properties of the family of maximum stable sets of a graph, Constraints on the number of maximal independent sets in graphs, On Trees of Bounded Degree with Maximal Number of Greatest Independent Sets, Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter, Trees with maximum number of maximal matchings, Maximizing the number of independent sets of fixed size in connected graphs with given independence number, The maximum number of maximum dissociation sets in trees, On the maximum number of maximum independent sets in connected graphs, Minimum \(d\)-blockers and \(d\)-transversals in graphs, Maximum dissociation sets in subcubic trees, On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number, Minimum number of maximal dissociation sets in trees, On the maximum number of maximum dissociation sets in trees with given dissociation number, On the independence graph of a graph, On local maximum stable set greedoids, On the maximum number of minimum dominating sets in forests, Null decomposition of bipartite graphs without cycles of length 0 modulo 4, Trees with extremal numbers of maximal independent sets including the set of leaves, Independent sets in graphs, Maximal independent sets and maximal matchings in series-parallel and related graph classes, On the maximum number of maximum independent sets, On \(\alpha\)-critical edges in König--Egerváry graphs, Trees with a given number of leaves and the maximal number of maximum independent sets, Graphs with the second largest number of maximal independent sets, On the \(k\)-component independence number of a tree, Unnamed Item, A finiteness theorem for maximal independent sets, The number of maximal independent sets in connected triangle-free graphs, Counting stable sets on Cartesian products of graphs, On the number of vertices belonging to all maximum stable sets of a graph, A new greedoid: The family of local maximum stable sets of a forest, Trees with minimum number of infima closed sets

Cites Work

• Graphs whose vertex independence number is unaffected by single edge addition or deletion