The Number of Maximal Independent Sets in Triangle-Free Graphs
From MaRDI portal
Publication:4695389
DOI10.1137/0406022zbMath0779.05025OpenAlexW2035645338MaRDI QIDQ4695389
Publication date: 12 January 1994
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0406022
Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
The number of maximal independent sets in trees with a given number of leaves ⋮ An upper bound on the number of cliques in a graph ⋮ THE TYPICAL STRUCTURE OF MAXIMAL TRIANGLE-FREE GRAPHS ⋮ Maximal and maximum dissociation sets in general and triangle-free graphs ⋮ Counting maximal antichains and independent sets ⋮ On maximal sum-free sets in abelian groups ⋮ On Independent Sets and Bicliques in Graphs ⋮ A sharp bound on the number of maximal sum-free sets ⋮ On Trees of Bounded Degree with Maximal Number of Greatest Independent Sets ⋮ The number of the maximal triangle-free graphs ⋮ Minimal dominating sets in interval graphs and trees ⋮ Maximal independent sets in graphs with at most one cycle ⋮ On solution-free sets of integers ⋮ Trees with maximum number of maximal matchings ⋮ Enumeration and maximum number of minimal connected vertex covers in graphs ⋮ The number of maximal sum-free subsets of integers ⋮ The second largest number of maximal independent sets in connected graphs with at most one cycle ⋮ Maximal independent sets in clique-free graphs ⋮ The number of maximal independent sets in the Hamming cube ⋮ Bounds on the Number of Maximal Sum-Free Sets ⋮ On the number of maximal independent sets: From Moon–Moser to Hujter–Tuza ⋮ On radius 2 trees with the maximum number of matchings ⋮ Some bounds on the size of maximum G-free sets in graphs ⋮ Maximal independent sets in grid graphs ⋮ On the Number ofk-Dominating Independent Sets ⋮ Maximum number of fixed points in AND-OR-NOT networks ⋮ The maximum number of maximal independent sets in unicyclic connected graphs ⋮ On the number of minimal transversals in 3-uniform hypergraphs ⋮ Independent sets in graphs ⋮ Enumerating solution-free sets in the integers ⋮ Exact algorithms for exact satisfiability and number of perfect matchings ⋮ Groups with few maximal sum-free sets ⋮ Enumerating maximal independent sets with applications to graph colouring. ⋮ On graphs with the third largest number of maximal independent sets ⋮ 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 ⋮ Satisfiability of mixed Horn formulas ⋮ Graphs with the second largest number of maximal independent sets ⋮ Maximal Induced Matchings in Triangle-Free Graphs ⋮ Maximal independent sets and regularity of graphs ⋮ Maximum weight independent sets for (\(S_{1,2,4}\),triangle)-free graphs in polynomial time ⋮ Trees without twin-leaves with smallest number of maximal independent sets ⋮ Independent sets in \((P_4+P_4\),triangle)-free graphs ⋮ Enumerating Minimal Dominating Sets in Triangle-Free Graphs ⋮ Stability for maximal independent sets ⋮ Maximal independent sets in caterpillar graphs ⋮ Bounds on the number of maximal sum-free sets ⋮ A finiteness theorem for maximal independent sets ⋮ The number of maximal independent sets in connected triangle-free graphs ⋮ Trees with the second largest number of maximal independent sets
This page was built for publication: The Number of Maximal Independent Sets in Triangle-Free Graphs
