The maximum number of maximum generalized 4-independent sets in trees
type: Item
instance of: scholarly article
title: The maximum number of maximum generalized 4-independent sets in trees
zbMATH Open document ID: 1548.05184
author: Pingshan Li
author: Min Xu
published in: Journal of Graph Theory
publication date: 2024-09-16T00:00:00Z
review text: A generalized \(k\)-independent set is a set of vertices such that the induced subgraph contains no trees with \(k\) vertices, and the generalized \(k\)-independence number of \(G\) is the cardinality of a maximum generalized \(k\)-independent set in \(G\). \N\NNote that a generalized \(2\)-independent set is an independent set. Hence generalized \(k\)-independent set is a generalization of independent set. \N\NIn this paper, the authors ``establish four structure theorems about maximum generalized \(k\)-independent sets in a tree for a general integer \(k\). As applications, we show that the maximum number of generalized 4-independent sets in a tree of order \(n\) \((n\geq 4)\) is\N\[\N\begin{cases}\N4^{\frac{n-4}{4}}+(\frac{n}{4}+1)(\frac{n}{8}+1), & n\equiv 0 \pmod{4}, \\\N4^{\frac{n-5}{4}}+\frac{n-1}{4}+1, & n\equiv 1\pmod{4}, \\\N4^{\frac{n-6}{4}}+\frac{n-2}{4}, & n\equiv 2 \pmod{4}, \\\N4^{\frac{n-7}{4}}, & n\equiv 3\pmod{4},\N\end{cases}\N\]\Nand we also characterize the structure of all extremal trees with the maximum number of maximum generalized 4-independent sets''.
reviewed by: Leilei Zhang
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 7914203
zbMATH Keywords: dissociation sets
zbMATH Keywords: \(k\)-independent sets
zbMATH Keywords: König-Egerváry graphs
zbMATH Keywords: tree
MaRDI profile type: Publication
cites work: NP-hard graph problems and boundary classes of graphs
cites work: An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth
cites work: Q5463498
cites work: Minimum \(k\)-path vertex cover
cites work: Independent packings in structured graphs
cites work: The number of maximal independent sets in connected graphs
cites work: Maximal independent sets in graphs with at mostr cycles
cites work: The number of maximal independent sets in a connected graph
cites work: The Number of Maximal Independent Sets in Triangle-Free Graphs
cites work: On the \(k\)-path vertex cover of some graph products
cites work: Maximal independent sets in graphs with at most one cycle
cites work: The maximum number of maximal independent sets in unicyclic connected graphs
cites work: On cliques in graphs
cites work: The complexity of dissociation set problems in graphs
cites work: A Note on Independent Sets in Trees
cites work: Maximal and maximum independent sets in graphs with at mostr cycles
cites work: The maximum number of maximum dissociation sets in trees
cites work: The Number of Maximal Independent Sets in a Tree
cites work: Node-Deletion Problems on Bipartite Graphs
cites work: The structure and maximum number of maximum independent sets in trees
DOI: 10.1002/JGT.23122
description: scientific article; zbMATH DE number 7914203