The maximum number of maximum dissociation sets in trees

Tu Jianhua, Zhang Zhipeng, Shi Yongtang

Published 2019-11-19Version 1

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.