Minimum number of maximal dissociation sets in trees

DOI10.1016/j.dam.2024.01.008OpenAlexW4391055491WikidataQ129666716 ScholiaQ129666716MaRDI QIDQ6193972

Jian Guo Qian, Junxia Zhang, Sumin Huang

Publication date: 14 February 2024

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

Full work available at URL: https://doi.org/10.1016/j.dam.2024.01.008

zbMATH Keywords

treeextremal graphmaximal dissociation set

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Vertex degrees (05C07) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Bounds on the maximum number of minimum dominating sets
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• The maximum number of maximal independent sets in unicyclic connected graphs
• Trees with extremal numbers of maximal independent sets including the set of leaves
• On the number of independent sets in a tree
• NP-completeness of some generalizations of the maximum matching problem
• Enumeration and maximum number of minimal connected vertex covers in graphs
• On the maximum number of minimum dominating sets in forests
• Exact algorithms for maximum independent set
• Maximal and maximum dissociation sets in general and triangle-free graphs
• Minimum \(k\)-path vertex cover
• The complexity of dissociation set problems in graphs
• Almost all trees have an even number of independent sets
• An Improved Exact Algorithm for Maximum Induced Matching
• Improper coloring of unit disk graphs
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Maximal and maximum independent sets in graphs with at mostr cycles
• The Number of Maximal Independent Sets in a Tree
• Node-Deletion Problems on Bipartite Graphs
• The structure and maximum number of maximum independent sets in trees
• Constraints on the number of maximal independent sets in graphs
• Maximum $r$-Regular Induced Subgraph Problem: Fast Exponential Algorithms and Combinatorial Bounds
• Maximal Induced Matchings in Triangle-Free Graphs
• Algorithms and Computation
• The maximum number of maximum dissociation sets in trees
• On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number

This page was built for publication: Minimum number of maximal dissociation sets in trees