REVIEW 2 cited by
Maximizing the number of maximal independent sets of a fixed size
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
read the original 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.
Forward citations
Cited by 2 Pith papers
-
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.
-
Twin-free $K_r$-saturated Graphs and Maximally Independent Sets in $K_3$-free Graphs
For twin-free K_r-saturated graphs, the minimum edge count is asymptotically between (r+2)n and (r+3)n, and for triangles between (5+2/3)n and 6n.
Discussion (0). Continue with ORCID to comment.