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)

Cites Work

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

Related Items (35)

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 maximum number of maximum independent sets of bipartite graphs ⋮ The maximum number of maximum generalized 4-independent sets in trees ⋮ 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

This page was built for publication: The structure and maximum number of maximum independent sets in trees