The Number of Maximal Independent Sets in a Tree
From MaRDI portal
Publication:3708817
DOI10.1137/0607015zbMath0584.05024OpenAlexW1973664393MaRDI QIDQ3708817
Publication date: 1986
Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/998c22aea3babc3de2a85489211eceb03ddad8fc
Trees (05C05) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Related Items (42)
The number of maximal independent sets in trees with a given number of leaves ⋮ Graphs, partitions and Fibonacci numbers ⋮ Maximal and maximum dissociation sets in general and triangle-free graphs ⋮ Constraints on the number of maximal independent sets in graphs ⋮ The number of maximal independent sets in a connected graph ⋮ On Trees of Bounded Degree with Maximal Number of Greatest Independent Sets ⋮ Maximal independent sets in graphs with at most one cycle ⋮ Maximal independent sets on a grid graph ⋮ Maximum modulus of independence roots of graphs and trees ⋮ Trees with maximum number of maximal matchings ⋮ Maximal independent sets in clique-free graphs ⋮ The maximum number of maximum dissociation sets in trees ⋮ Counting maximal independent sets in some \(n\)-gonal cacti ⋮ Generalizing Erdős, Moon and Moser's result -- the number of \(k\)-dominating independent sets ⋮ On the number of maximal independent sets: From Moon–Moser to Hujter–Tuza ⋮ The number of maximum matchings in a tree ⋮ Maximum dissociation sets in subcubic trees ⋮ Minimum number of maximal dissociation sets in trees ⋮ On the maximum number of maximum dissociation sets in trees with given dissociation number ⋮ On the Number ofk-Dominating Independent Sets ⋮ The maximum number of maximal independent sets in unicyclic connected graphs ⋮ On the number of minimal transversals in 3-uniform hypergraphs ⋮ 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 ⋮ The inverse problem for certain tree parameters ⋮ On graphs with the third largest number of maximal independent sets ⋮ Counting maximal independent sets in directed path graphs ⋮ The number of maximal independent sets of \((k+1)\)-valent trees ⋮ Coverings, Matchings and the number of maximal independent sets of graphs ⋮ Trees with a given number of leaves and the maximal number of maximum independent sets ⋮ On the maximum number of cliques in a graph ⋮ Graphs with the second largest number of maximal independent sets ⋮ Maximal independent sets and maximal matchings in series-parallel and related graph classes ⋮ Maximal independent sets and regularity of graphs ⋮ Trees without twin-leaves with smallest number of maximal independent sets ⋮ Maximal independent sets in caterpillar graphs ⋮ 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 ⋮ The maximum clique problem ⋮ Trees with minimum number of infima closed sets
Cites Work
This page was built for publication: The Number of Maximal Independent Sets in a Tree
