{
  "id": "2012.06066",
  "version": "v2",
  "published": "2020-12-11T01:08:36.000Z",
  "updated": "2020-12-19T01:21:19.000Z",
  "title": "Maximizing the number of maximal independent sets of a fixed size",
  "authors": [
    "Chunwei Song",
    "Bowen Yao"
  ],
  "comment": "4 pages",
  "categories": [
    "math.CO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2020-12-19T01:21:19.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "05C69",
      "05D99",
      "05C31"
    ],
    "keywords": [
      "maximal independent set",
      "fixed size",
      "extremal graphs",
      "maximizing",
      "maximum number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 4,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}