Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419722 | Discrete Applied Mathematics | 2013 | 6 Pages |
Abstract
Several familiar problems in extremal set theory can be cast as questions about the maximum possible size of an independent set defined on a suitable graph, about the total number of independent sets in such graphs, or about enumeration of the maximal independent sets. Here we find bounds on the number of maximal independent sets in the covering graph of a hypercube.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Dwight Duffus, Peter Frankl, Vojtěch Rödl,