On the k-Component Independence Number of a Tree

Shuting Cheng, Baoyindureng Wu and Fabio Tramontana

Discrete Dynamics in Nature and Society, 2021, vol. 2021, 1-4

Abstract: Let G be a graph and k≥1 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 GS has order at most k. The k-component independence number, denoted by αckG, 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 αkT≥k/k+1n. The bound is sharp. In addition, we give a linear-time algorithm for finding a maximum k-component independent set of a tree.

Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/ddns/2021/5540604.pdf (application/pdf)
http://downloads.hindawi.com/journals/ddns/2021/5540604.xml (application/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnddns:5540604

DOI: 10.1155/2021/5540604

Access Statistics for this article

More articles in Discrete Dynamics in Nature and Society from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().