{
  "id": "1911.08154",
  "version": "v1",
  "published": "2019-11-19T08:23:34.000Z",
  "updated": "2019-11-19T08:23:34.000Z",
  "title": "The maximum number of maximum dissociation sets in trees",
  "authors": [
    "Tu Jianhua",
    "Zhang Zhipeng",
    "Shi Yongtang"
  ],
  "comment": "19 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A subset of vertices is a {\\it maximum independent set} if no two of the vertices are adjacent and the subset has maximum cardinality. A subset of vertices is called a {\\it maximum dissociation set} if it induces a subgraph with vertex degree at most 1, and the subset has maximum cardinality. Zito [J. Graph Theory {\\bf 15} (1991) 207--221] proved that the maximum number of maximum independent sets of a tree of order $n$ is $2^{\\frac{n-3}{2}}$ if $n$ is odd, and $2^{\\frac{n-2}{2}}+1$ if $n$ is even and also characterized all extremal trees with the most maximum independent sets, which solves a question posed by Wilf. Inspired by the results of Zito, in this paper, by establishing four structure theorems and a result of $k$-K\\\"{o}nig-Egerv\\'{a}ry graph, we show that the maximum number of maximum dissociation sets in a tree of order $n$ is \\begin{center} $\\left\\{ \\begin{array}{ll} 3^{\\frac{n}{3}-1}+\\frac{n}{3}+1, & \\hbox{if $n\\equiv0\\pmod{3}$;} 3^{\\frac{n-1}{3}-1}+1, & \\hbox{if $n\\equiv1\\pmod{3}$;} 3^{\\frac{n-2}{3}-1}, & \\hbox{if $n\\equiv2\\pmod{3}$,} \\end{array} \\right.$ \\end{center} and also give complete structural descriptions of all extremal trees on which these maxima are achieved.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-11-19T08:23:34.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "maximum dissociation set",
      "maximum number",
      "maximum independent set",
      "extremal trees",
      "maximum cardinality"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}