The maximum number of maximum dissociation sets in trees

DOI10.1002/jgt.22627zbMath1521.05026arXiv1911.08154OpenAlexW3091524897MaRDI QIDQ6055404

Jian-hua Tu, Yongtang Shi, Zhipeng Zhang

Publication date: 29 September 2023

Published in: Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

treedissociation setKönig-Egerváry graphs

Mathematics Subject Classification ID

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

Related Items (9)

Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree ⋮ Maximal and maximum dissociation sets in general and triangle-free graphs ⋮ Maximum weight t-sparse set problem on vector-weighted graphs ⋮ Maximum dissociation sets in subcubic trees ⋮ On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number ⋮ Extremal vertex-degree function index with given order and dissociation number ⋮ On spectral extrema of graphs with given order and dissociation number ⋮ Minimum number of maximal dissociation sets in trees ⋮ On the maximum number of maximum dissociation sets in trees with given dissociation number

Cites Work

• Unnamed Item
• Unnamed Item
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• Combinatorial and spectral properties of König-Egerváry graphs
• A characterization of the graphs in which the transversal number equals the matching number
• 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
• Ear-decompositions of matching-covered graphs
• The number of maximal independent sets in a connected graph
• On the maximum number of minimum dominating sets in forests
• Minimum \(k\)-path vertex cover
• The complexity of dissociation set problems in graphs
• Almost all trees have an even number of independent sets
• Two more characterizations of König-Egerváry graphs
• NP-hard graph problems and boundary classes of graphs
• Independent packings in structured graphs
• A characterization of Konig-Egervary graphs using a common property of all maximum matchings
• 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 complexity of restricted spanning tree problems
• The structure and maximum number of maximum independent sets in trees
• Constraints on the number of maximal independent sets in graphs
• An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth

This page was built for publication: The maximum number of maximum dissociation sets in trees