On the -Component Independence Number of a Tree

[摘要] Let be a graph and be an integer. A subset of vertices in a graph is called a - component independent set of if each component of has order at most . The - component independence number, denoted by , is the maximum order of a vertex subset that induces a subgraph with maximum component order at most . We prove that if a tree is of order , then . The bound is sharp. In addition, we give a linear-time algorithm for finding a maximum - component independent set of a tree.

[学科分类] 安全、风险、质量和可靠性