{"id":"arxiv/2608.16639","url":"https://arxiv.org/abs/2608.16639","tags":["math.CO"],"score":0,"title":"The maximum number of maximal dissociation sets in trees","domain":"math.CO","source":"arxiv","authors":["Meiqin Wang","Min Xu","Ning Zhang"],"reviews":0,"subject":"math.CO","summary":"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\\geq 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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-17","reactions":{}}