On the k-component independence number of a tree

DOI10.1155/2021/5540604MaRDI QIDQ2045314zbMATH OpenOpenAlexFDO

Authors Shuting Cheng, Baoyindureng Wu

Publication date 12 August 2021

Published in Discrete Dynamics in Nature and Society (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1155/2021/5540604

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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.

Recommendations

• Domination, independent domination and \(k\)-independence in trees
• A characterization of trees for a new lower bound on the k-independence number
• Independence number and \(k\)-trees of graphs
• Independence polynomials of \(k\)-tree related graphs
• scientific article; zbMATH DE number 2192183

Cites work

• (Strong) conflict-free connectivity: algorithm and complexity
• Bounded monochromatic components for random graphs
• Bounded size components -- partitions and transversals.
• Clustered colouring in minor-closed classes
• Conflict-free (vertex-)connection numbers of graphs with small diameters
• Defective and clustered graph colouring
• Fragmentability of graphs
• Graphs with the second largest number of maximal independent sets
• Maximum value of conflict-free vertex-connection number of graphs
• New upper bounds on harmonious colorings
• On conflict-free connection of graphs
• On subgraphs without large components.
• On the maximum number of maximum independent sets
• Partitioning into graphs with only small components
• Partitioning sparse graphs into an independent set and a graph with bounded size components
• The number of maximum independent sets in graphs
• The structure and maximum number of maximum independent sets in trees
• Topics in structural graph theory

Cited in

(5)

• On subgraph number independence in trees
• On the asymptotic behavior of the independence number of a random (n,n)-tree
• On the independence number of some random trees
• scientific article; zbMATH DE number 32144 (Why is no real title available?)
• scientific article; zbMATH DE number 179305 (Why is no real title available?)

This page was built for publication: On the \(k\)-component independence number of a tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2045314)