2019/11/19 by Jianhua, Tu, Zhipeng, Zhang, Yongtang, Shi · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1911.08154
A subset of vertices is a \it maximum independent set if no two of the vertices are adjacent and the subset has maximum cardinality. A subset of vertices is called a \it maximum dissociation set if it induces a subgraph with vertex degree at most 1, and the subset has maximum cardinality. Zito [J. Graph Theory \bf 15 (1991) 207--221] proved that the maximum number of maximum independent sets of a tree of order n is 2(n-3)/(2) if n is odd, and 2(n-2)/(2)+1 if n 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-König-Egerváry graph, we show that the maximum number of maximum dissociation sets in a tree of order n is \ 3(n)/(3)-1+(n)/(3)+1, · amp; \hboxif n≡0\pmod3; 3(n-1)/(3)-1+1, · amp; \hboxif n≡1\pmod3; 3(n-2)/(3)-1, · amp; \hboxif n≡2\pmod3, . and also give complete structural descriptions of all extremal trees on which these maxima are achieved.