The maximum number of maximum dissociation sets in trees
From MaRDI portal
Publication:6055404
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
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
