The maximum number of maximum dissociation sets in trees
Jianhua Tu, Zhipeng Zhang, Yongtang Shi
Abstract
Abstract A subset of vertices is a maximum independent set if no two of the vertices are adjacent and the subset has maximum cardinality. A subset of vertices is called a maximum dissociation set if it induces a subgraph with vertex degree at most 1, and the subset has maximum cardinality. Zito proved that the maximum number of maximum independent sets of a tree of order is if is odd, and if is even and also characterized all extremal trees with the most maximum independent sets, which solved a question posed by Wilf. Inspired by the results of Zito, in this paper, by establishing four structure theorems and a result of ‐König–Egerváry graph, we show that the maximum number of maximum dissociation sets in a tree of order is and also give complete structural descriptions of all extremal trees on which these maxima are achieved.