Let be a simple graph. A dissociation set of proposed by Yannakakis in is defined as a set of vertices that induces a subgraph in which every vertex has a degree of at most . A dissociation set is maximal if it is not contained as a proper subset in any other dissociation set. In , Wang et al.\cite{ZiyuanWang} established that for any tree of order , the number of maximal dissociation sets in is at most 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 is , where We also characterize the extremal trees with the maximum number of maximal dissociation sets.

生成讲解博客的中文版本

生成AI智能校验的中文版本