Research article

Number of maximal 2-component independent sets in forests

  • Received: 03 January 2022 Revised: 03 April 2022 Accepted: 11 April 2022 Published: 20 May 2022
  • MSC : 05C30, 05C69

  • 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

    Related Papers:

  • 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
  • Reader Comments
  • © 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(1403) PDF downloads(49) Cited by(0)

Article outline

Figures and Tables

Figures(12)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog