An upper bound for the number of maximal independent sets in a graph

DOI10.1515/dma.2007.030zbMath1247.05166OpenAlexW1966756977MaRDI QIDQ5439059

Vladimir E. Alekseev

Publication date: 8 February 2008

Published in: Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1515/dma.2007.030

zbMATH Keywords

maximal independent setsBalas-Yu conjecture

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (6)

Some properties of intersection graph of a module with an application of the graph of ℤ_n ⋮ Blocker size via matching minors ⋮ Clique problem, cutting plane proofs and communication complexity ⋮ Systems of parameters and the Cohen-Macaulay property ⋮ Independent sets in graphs ⋮ An upper bound for the number of independent sets in regular graphs

Cites Work

• On graphs with polynomially solvable maximum-weight clique problem
• A New Algorithm for Generating All the Maximal Independent Sets
• An upper bound on the number of cliques in a graph
• On cliques in graphs

This page was built for publication: An upper bound for the number of maximal independent sets in a graph