The maximum number of maximum generalized 4-independent sets in trees (Q6606325)

A generalized \(k\)-independent set is a set of vertices such that the induced subgraph contains no trees with \(k\) vertices, and the generalized \(k\)-independence number of \(G\) is the cardinality of a maximum generalized \(k\)-independent set in \(G\). \N\NNote that a generalized \(2\)-independent set is an independent set. Hence generalized \(k\)-independent set is a generalization of independent set. \N\NIn this paper, the authors ``establish four structure theorems about maximum generalized \(k\)-independent sets in a tree for a general integer \(k\). As applications, we show that the maximum number of generalized 4-independent sets in a tree of order \(n\) \((n\geq 4)\) is\N\[\N\begin{cases}\N4^{\frac{n-4}{4}}+(\frac{n}{4}+1)(\frac{n}{8}+1), & n\equiv 0 \pmod{4}, \\\N4^{\frac{n-5}{4}}+\frac{n-1}{4}+1, & n\equiv 1\pmod{4}, \\\N4^{\frac{n-6}{4}}+\frac{n-2}{4}, & n\equiv 2 \pmod{4}, \\\N4^{\frac{n-7}{4}}, & n\equiv 3\pmod{4},\N\end{cases}\N\]\Nand we also characterize the structure of all extremal trees with the maximum number of maximum generalized 4-independent sets''.