For 2-CNF formulas the maximum number of accepted weight-t assignments is q^{n-t-r}(q+1)^r, and for t=n-k the general problem is equivalent to the Turán problem.
Maximizing the number of maximal independent sets of a fixed size
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
For a fixed graph G, a maximal independent set is an independent set that is not a proper subset of any other independent set. P. Erd\"os, and independently, J. W. Moon and L. Moser, and R. E. Miller and D. E. Muller, determined the maximum number of maximal independent sets in a graph on n vertices, as well as the extremal graphs. In this paper we maximize the number of maximal independent sets of a fixed size for all graphs of order n and determine the extremal graphs. Our result generalizes the classical result.
fields
cs.CC 1years
2024 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
On Extremal Properties of k-CNF: Capturing Threshold Functions
For 2-CNF formulas the maximum number of accepted weight-t assignments is q^{n-t-r}(q+1)^r, and for t=n-k the general problem is equivalent to the Turán problem.