Number of maximal 2-component independent sets in forests

Abstract

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. $

Keywords

• tree
• forest
• independent set
• k-component independent set