@article{Cheng2022, 
author = {Shuting Cheng and Baoyindureng Wu},
title = {Number of maximal 2-component independent sets in forests},
year = {2022},
journal = {AIMS Mathematics},
volume = {7},
number = {7},
pages = {13537-13562},
keywords = {tree, forest, independent set, k-component independent set},
url = {https://www.sciopen.com/article/10.3934/math.2022748},
doi = {10.3934/math.2022748},
abstract = {Let    G  =  (  V  (  G  )  ,  E  (  G  )  ) be a graph. For a positive integer    k, we call    S  ⊆  V  (  G  ) a    k-component independent set of    G if each component of    G  [  S  ] has order at most    k. Moreover,    S is maximal if there does not exist a    k-component independent set        S    ′   of    G such that    S  ⊆      S    ′   and        |    S      |    <      |        S    ′        |  . A maximal    k-component independent set of a graph    G is denoted briefly by Mk-CIS. We use        t    k    (  G  ) to denote the number of Mk-CISs of a graph    G. In this paper, we show that for a forest    G of order    n,         t    2    (  G  )  ≤      {                                        3                                          n                3                                              ,                          if                                n            ≡            0                        (            m            o            d                        3            )                        and                        n            ≥            3                    ,                                      4          ⋅                      3                                                            n                  −                  4                                3                                              ,                          if                                n            ≡            1                        (            m            o            d                        3            )                        and                        n            ≥            4                    ,                                      5          ,                          if                                n            =            5                    ,                                                  4                          2                                ⋅                      3                                                            n                  −                  8                                3                                              ,                          if                                n            ≡            2                        (            m            o            d                        3            )                        and                        n            ≥            8                    ,                        with equality if and only if    G  ≅      F    n  , where         F    n    ≅      {                                        n            3                                P                          3                                ,                          if                                n            ≡            0                        (            m            o            d                        3            )                        and                        n            ≥            3                    ,                                                                n              −              4                        3                                P                          3                                ∪                      K                          1              ,              3                                ,                          if                                n            ≡            1                        (            m            o            d                        3            )                        and                        n            ≥            4                    ,                                                  K                          1              ,              4                                ,                          if                                n            =            5                    ,                                                                n              −              8                        3                                P                          3                                ∪          2                      K                          1              ,              3                                ,                          if                                n            ≡            2                        (            m            o            d                        3            )                        and                        n            ≥            8                    .}
}