The maximum number of maximum generalized 4‐independent sets in trees

Abstract A generalized ‐independent set is a set of vertices such that the induced subgraph contains no trees with ‐vertices, and the generalized ‐independence number is the cardinality of a maximum ‐independent set in . Zito proved that the maximum number of maximum generalized 2‐independent sets in a tree of order is if is odd, and if is even. Tu et al. showed that the maximum number of maximum generalized 3‐independent sets in a tree of order is if , and if , and if and they characterized all the extremal graphs. Inspired by these two nice results, we establish four structure theorems about maximum generalized ‐independent sets in a tree for a general integer . As applications, we show that the maximum number of generalized 4‐independent sets in a tree of order is and we also characterize the structure of all extremal trees with the maximum number of maximum generalized 4‐independent sets.