On the \(k\)-component independence number of a tree
type: Item
instance of: scholarly article
title: On the \(k\)-component independence number of a tree
zbMATH Open document ID: 1471.05077
DOI: 10.1155/2021/5540604
author: Shuting Cheng
author: Baoyindureng Wu
published in: Discrete Dynamics in Nature and Society
publication date: 2021-08-12T00:00:00Z
review text: Summary: Let \(G\) be a graph and \(k\geq1\) be an integer. A subset \(S\) of vertices in a graph \(G\) is called a \(k\)-component independent set of \(G\) if each component of \(G[S]\) has order at most \(k\). The \(k\)-component independence number, denoted by \(\alpha_c^k(G)\), is the maximum order of a vertex subset that induces a subgraph with maximum component order at most \(k\). We prove that if a tree \(T\) is of order \(n\), then \(\alpha_k(T)\geq(k/(k+1))n\). The bound is sharp. In addition, we give a linear-time algorithm for finding a maximum \(k\)-component independent set of a tree.
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 7381269
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2021/5540604
OpenAlex ID: W3166777523
cites work: Bounded monochromatic components for random graphs
cites work: Partitioning into graphs with only small components
cites work: On subgraphs without large components
cites work: Partitioning sparse graphs into an independent set and a graph with bounded size components
cites work: Islands in Graphs on Surfaces
cites work: Bounded size components -- partitions and transversals.
cites work: Graph coloring with no large monochromatic components
cites work: Clustered colouring in minor-closed classes
cites work: Defective and clustered graph colouring
cites work: New upper bounds on harmonious colorings
cites work: Fragmentability of graphs
cites work: Topics in structural graph theory
cites work: Maximum value of conflict-free vertex-connection number of graphs
cites work: On conflict-free connection of graphs
cites work: Conflict-free (vertex)-connection numbers of graphs with small diameters
cites work: (Strong) conflict-free connectivity: algorithm and complexity
cites work: The structure and maximum number of maximum independent sets in trees
cites work: Graphs with the second largest number of maximal independent sets
cites work: The number of maximum independent sets in graphs
cites work: On the maximum number of maximum independent sets
description: scientific article; zbMATH DE number 7381269