Let $ G = (V(G), E(G)) $ be a graph. For a positive integer $ k $, we call $ S\subseteq 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\subseteq 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)\leq \left\{ \begin{array}{ll} 3^{\frac{n} 3 },& \text{if}\quad { n\equiv 0\ (mod\ 3) \; \text{and} \; n\geq3 },\\ 4 \cdot 3^{\frac{n-4} 3 },& \text{if}\quad { n \equiv 1\ (mod\ 3) \; \text{and} \; n\geq 4 },\\ 5,& \text{if}\quad { n = 5 },\\ 4^{2} \cdot 3^{\frac{n-8} 3 },& \text{if}\quad { n\equiv 2\ (mod\ 3) \; \text{and} \; n\geq 8 }, \end{array} \right. $
with equality if and only if $ G\cong F_n $, where
$ F_n \cong \left\{ \begin{array}{ll} \frac n 3 P_{3},& \text{if}\quad { n\equiv 0\ ( mod\ 3) \; \text{and} \; n\geq 3 },\\ \frac {n-4} 3 P_{3}\cup K_{1,3} ,& \text{if}\quad { n \equiv 1\ ( mod\ 3) \; \text{and} \; n\geq 4 },\\ K_{1,4} ,& \text{if}\quad { n = 5 },\\ \frac {n-8} 3 P_{3}\cup 2K_{1,3},& \text{if}\quad { n\equiv 2\ ( mod\ 3) \; \text{and} \; n\geq 8 }. \end{array} \right. $
Citation: Shuting Cheng, Baoyindureng Wu. Number of maximal 2-component independent sets in forests[J]. AIMS Mathematics, 2022, 7(7): 13537-13562. doi: 10.3934/math.2022748
Let $ G = (V(G), E(G)) $ be a graph. For a positive integer $ k $, we call $ S\subseteq 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\subseteq 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)\leq \left\{ \begin{array}{ll} 3^{\frac{n} 3 },& \text{if}\quad { n\equiv 0\ (mod\ 3) \; \text{and} \; n\geq3 },\\ 4 \cdot 3^{\frac{n-4} 3 },& \text{if}\quad { n \equiv 1\ (mod\ 3) \; \text{and} \; n\geq 4 },\\ 5,& \text{if}\quad { n = 5 },\\ 4^{2} \cdot 3^{\frac{n-8} 3 },& \text{if}\quad { n\equiv 2\ (mod\ 3) \; \text{and} \; n\geq 8 }, \end{array} \right. $
with equality if and only if $ G\cong F_n $, where
$ F_n \cong \left\{ \begin{array}{ll} \frac n 3 P_{3},& \text{if}\quad { n\equiv 0\ ( mod\ 3) \; \text{and} \; n\geq 3 },\\ \frac {n-4} 3 P_{3}\cup K_{1,3} ,& \text{if}\quad { n \equiv 1\ ( mod\ 3) \; \text{and} \; n\geq 4 },\\ K_{1,4} ,& \text{if}\quad { n = 5 },\\ \frac {n-8} 3 P_{3}\cup 2K_{1,3},& \text{if}\quad { n\equiv 2\ ( mod\ 3) \; \text{and} \; n\geq 8 }. \end{array} \right. $
[1] | V. E. Alekseev, R. Boliac, D. V. Korobitsyn, V. V. Lozin, NP-hard graph problems and boundary classes of graphs, Theor. Comput. Sci., 389 (2007), 219–236. https://doi.org/10.1016/j.tcs.2007.09.013 doi: 10.1016/j.tcs.2007.09.013 |
[2] | R. Boliac, K. Cameron, V. V. Lozin, On computing the dissociation number and the induced matching number of bipartite graphs, Ars Combin., 72 (2004), 241–253. |
[3] | S. Cheng, B. Wu, On the $k$-component independence number of a tree, Discrete Dyn. Nat. Soc., 2021, 5540604. |
[4] | M. Hujter, Z. Tuza, The number of maximal independent sets in triangle-free graphs, SIAM J. Discrete Math., 6 (1993), 284–288. https://doi.org/10.1137/0406022 doi: 10.1137/0406022 |
[5] | M. J. Jou, G. J. Chang, Maximal independent sets in graphs with at most one cycle, Discrete Appl. Math., 79 (1997), 67–73. https://doi.org/10.1016/S0166-218X(97)00033-4 doi: 10.1016/S0166-218X(97)00033-4 |
[6] | K. M. Koh, C. Y. Goh, F. M. Dong, The maximum number of maximal independent sets in unicyclic connected graphs, Discrete Math., 308 (2008), 3761–3769. doilinkhttps://doi.org/10.1016/j.disc.2007.07.079 doi: 10.1016/j.disc.2007.07.079 |
[7] | Y. Orlovich, A. Dolguib, G. Finkec, V. Gordond, F. Wernere, The complexity of dissociation set problems in graphs, Discrete Appl. Math., 159 (2011) 1352–1366. https://doi.org/10.1016/j.dam.2011.04.023 |
[8] | C. H. Papadimitriou, M. Yannakakis, The complexity of restricted spanning tree problems, J. Assoc. Comput. Mach., 29 (1982), 285–309. https://doi.org/10.1145/322307.322309 doi: 10.1145/322307.322309 |
[9] | B. E. Sagan, A note on independent sets in trees, SIAM J. Discrete Math., 1 (1988), 105–108. https://doi.org/10.1137/0401012 doi: 10.1137/0401012 |
[10] | B. E. Sagan, V. R. Vatter, Maximal and maximum independent sets in graphs with at most $r$ cycles, J. Graph Theory, 53 (2006), 283–314. https://doi.org/10.1002/jgt.20186 doi: 10.1002/jgt.20186 |
[11] | J. Tu, Z. Zhang, Y. Shi, The maximum number of maximum dissociation sets in trees, J. Graph Theory, 96 (2021), 472–489. https://doi.org/10.1002/jgt.22627 doi: 10.1002/jgt.22627 |
[12] | H. S. Wilf, The number of maximal independent sets in a tree, SIAM J. Alg. Discrete Methods, 7 (1986), 125–130. https://doi.org/10.1137/0607015 doi: 10.1137/0607015 |
[13] | I. Wloch, Trees with extremal numbers of maximal independent sets including the set of leaves, Discrete Math., 308 (2008), 4768–4772. https://doi.org/10.1016/j.disc.2007.08.087 doi: 10.1016/j.disc.2007.08.087 |
[14] | M. Yannakakis, Node-deletion problems on bipartite graphs, SIAM J. Comput., 10 (1981), 310–327. https://doi.org/10.1137/0210022 doi: 10.1137/0210022 |
[15] | J. Zito, The structure and maximum number of maximum independent sets in trees, J. Graph Theory, 15 (1991), 207–221. https://doi.org/10.1002/jgt.3190150208 doi: 10.1002/jgt.3190150208 |