Let T be a tree of order n≥ 3. A set S⊆ V(T) is a dissociation set if every vertex of the induced subgraph T[S] has degree at most 1, and it is maximal if it is inclusion-maximal among dissociation sets. Let Phi(T) denote the number of maximal dissociation sets of T. The conjecture asks whether [ max_| V(T)|=nPhi(T)=g(n), ] where [ g(n)= n,&n=3,4,5,6, 3^fracn-13+fracn-13,&n equiv 1 pmod 3, n≥ 7, 4· 3^fracn-53+n-5,&n equiv 2 pmod 3, n≥ 8, 16· 3^fracn-93+3n-25,&n equiv 0 pmod 3, n≥ 12, n≠ 21, 19,&n=9, 1349,&n=21. ] The associated extremal problem also asks for a characterization of all trees attaining this maximum.

Wang et al.’s conjecture on maximal dissociation sets in trees

Let $T$ be a tree of order $n\geq 3$ . A set $S\subseteq V(T)$ is a dissociation set if every vertex of the induced subgraph $T[S]$ has degree at most $1$ , and it is maximal if it is inclusion-maximal among dissociation sets. Let $\Phi(T)$ denote the number of maximal dissociation sets of $T$ . The conjecture asks whether

\max_{\lvert V(T)\rvert=n}\Phi(T)=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\geq 7,\\ 4\cdot 3^{\frac{n-5}{3}}+n-5,&n\equiv 2\pmod 3,\ n\geq 8,\\ 16\cdot 3^{\frac{n-9}{3}}+3n-25,&n\equiv 0\pmod 3,\ n\geq 12,\ n\neq 21,\\ 19,&n=9,\\ 1349,&n=21. \end{cases}

The associated extremal problem also asks for a characterization of all trees attaining this maximum.

Progress summary

Solved

A new unrefereed preprint claims to settle the conjecture, but its result has not yet been independently verified.

Wang, Zhang, Tu, and Xiong proposed the conjecture in 2024 after proving a general upper bound for maximal dissociation sets in trees. The conjecture gives the exact maximum separately according to the residue of the tree order modulo $3$ .

Known results

Wang, Zhang, Tu, and Xiong (2024): for every tree of order $n \ge 4$ , $\Phi(T) \le 3^{(n-1)/3}+(n-1)/3$ .
Equality in that bound was characterized when $n \equiv 1 \pmod 3$ .
The cases $n \equiv 0,2 \pmod 3$ were left open and formed the conjecture.

August 2026 claimed resolution

A preprint dated August 17, 2026 claims the corrected piecewise function $g(n)$ is exact for every $n \ge 3$ , including exceptional values at $n=9$ and $n=21$ , and classifies all extremal trees. This is currently an unrefereed, unverified claim.

Current status (as of August 2026): The general bound and the $n \equiv 1 \pmod 3$ case are proved, while an August 2026 preprint claims the remaining cases and extremal classifications are solved but have not been independently verified.

Sources

arxiv.org

Sources & referencesView supporting material

Primary source

arXiv

Additional references

The maximum number of maximal dissociation sets in trees — arXiv — Wang, Meiqin, Xu, Min, Zhang, Ning

combinatorics extremal-graph-theory

1 day ago