{
  "id": "1805.02519",
  "version": "v1",
  "published": "2018-05-07T13:30:11.000Z",
  "updated": "2018-05-07T13:30:11.000Z",
  "title": "On the maximum number of maximum independent sets",
  "authors": [
    "Elena Mohr",
    "Dieter Rautenbach"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "We give a very short and simple proof of Zykov's generalization of Tur\\'{a}n's theorem, which implies that the number of maximum independent sets of a graph of order $n$ and independence number $\\alpha$ with $\\alpha<n$ is at most $\\left\\lceil\\frac{n}{\\alpha}\\right\\rceil^{n\\,{\\rm mod}\\,\\alpha} \\left\\lfloor\\frac{n}{\\alpha}\\right\\rfloor^{\\alpha-(n\\,{\\rm mod}\\,\\alpha)}$. Generalizing a result of Zito, we show that the number of maximum independent sets of a tree of order $n$ and independence number $\\alpha$ is at most $2^{n-\\alpha-1}+1$, if $2\\alpha=n$, and, $2^{n-\\alpha-1}$, if $2\\alpha>n$, and we also characterize the extremal graphs. Finally, we show that the number of maximum independent sets of a subcubic tree of order $n$ and independence number $\\alpha$ is at most $\\left(\\frac{1+\\sqrt{5}}{2}\\right)^{2n-3\\alpha+1}$, and we provide more precise results for extremal values of $\\alpha$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-05-07T13:30:11.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "maximum independent sets",
      "maximum number",
      "independence number",
      "zykovs generalization",
      "extremal values"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}