The maximum number of maximal dissociation sets in trees

Abstract

Let $G$ be a simple graph. A dissociation set of $G$ proposed by Yannakakis in $1981$ is defined as a set of vertices that induces a subgraph in which every vertex has a degree of at most $1$. A dissociation set is maximal if it is not contained as a proper subset in any other dissociation set. In $2025$, Wang et al.\cite{ZiyuanWang} established that for any tree $T$ of order $n\ge 4$, the number of maximal dissociation sets in $T$ is at most $3^{\frac{n-1}{3}}+\frac{n-1}{3}$ and characterized the extremal trees attaining the upper bound. They also proposed a conjecture about the upper bound of the maximal dissociation set. In this paper, we consider this conjecture and show that the maximum number of maximal dissociation sets in a tree of order $n(n\ge 3)$ is $g(n)$, where \[ g(n) = \begin{cases} n, & n=3,4,5,6,\\ 3^{\frac{n-1}{3}}+\frac{n-1}{3}, & n \equiv 1 \pmod{3},~n\geq7,\\ 4\cdot 3^{\frac{n-5}{3}}+n-5, & n \equiv 2 \pmod{3},~n\geq8, \\ 16\cdot 3^{\frac{n-9}{3}}+3n-25, & n \equiv 0 \pmod{3},~n\geq12~\text{and }~n\neq21, \\ 19, & n=9, \\ 1349, & n=21. \end{cases} \] We also characterize the extremal trees with the maximum number of maximal dissociation sets.