On the maximum number of maximum dissociation sets in trees with given dissociation number

DOI10.1016/j.disc.2024.113910arXiv2103.01407OpenAlexW3135818634MaRDI QIDQ6204327

Lei Zhang, Jun-feng Du, Jian-hua Tu

Publication date: 27 March 2024

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2103.01407

zbMATH Keywords

treeextremal enumerationdissociation numbermaximum dissociation set

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30)

Cites Work

• Unnamed Item
• Bounds on the maximum number of minimum dominating sets
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• A faster FPT algorithm for 3-path vertex cover
• The maximum number of maximal independent sets in unicyclic connected graphs
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• The number of maximal independent sets in a connected graph
• The number of maximal independent sets in connected triangle-free graphs
• Enumeration and maximum number of minimal connected vertex covers in graphs
• On the maximum number of minimum dominating sets in forests
• On the maximum number of maximum independent sets
• Many cliques with few edges
• Minimum \(k\)-path vertex cover
• The complexity of dissociation set problems in graphs
• The number of independent sets in an irregular graph
• NP-hard graph problems and boundary classes of graphs
• Independent packings in structured graphs
• Maximum Number of Minimal Feedback Vertex Sets in Chordal Graphs and Cographs
• Maximal independent sets in bipartite graphs
• Maximal and maximum independent sets in graphs with at mostr cycles
• The Number of Maximal Independent Sets in a Tree
• A Note on Independent Sets in Trees
• The number of maximal independent sets in connected graphs
• Node-Deletion Problems on Bipartite Graphs
• The structure and maximum number of maximum independent sets in trees
• The maximum number of triangles in a graph of given maximum degree
• Maximizing the Number of Independent Sets of a Fixed Size
• Maximal Induced Matchings in Triangle-Free Graphs
• On cliques in graphs
• The number of maximum independent sets in graphs
• The maximum number of maximum dissociation sets in trees
• On the maximum number of maximum independent sets in connected graphs

This page was built for publication: On the maximum number of maximum dissociation sets in trees with given dissociation number