On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number

DOI10.11650/TJM/230204zbMATH Open1520.05055OpenAlexW4323341728WikidataQ123121053 ScholiaQ123121053MaRDI QIDQ6178795FDOQ6178795

Authors: Wanting Sun, Shuchao Li 

Publication date: 5 September 2023

Published in: Taiwanese Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://projecteuclid.org/journals/taiwanese-journal-of-mathematics/volume-27/issue-4/On-the-Maximal-Number-of-Maximum-Dissociation-Sets-in-Forests/10.11650/tjm/230204.full

Recommendations

• The maximum number of maximum dissociation sets in trees
• Maximal and maximum dissociation sets in general and triangle-free graphs
• A bound on the dissociation number
• Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree
• Complexity of dissociate set problems in some hereditary classes of graphs

zbMATH Keywords

treeforestdissociation setdissociation number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

Cites Work

• Title not available (Why is that?)
• Minimum \(k\)-path vertex cover
• NP-hard graph problems and boundary classes of graphs
• On cliques in graphs
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• Node-Deletion Problems on Bipartite Graphs
• Maximal independent sets in minimum colorings
• Title not available (Why is that?)
• The complexity of restricted spanning tree problems
• Graphs with the second largest number of maximal independent sets
• On the maximum number of maximum independent sets
• The structure and maximum number of maximum independent sets in trees
• Title not available (Why is that?)
• Maximal independent sets in graphs with at mostr cycles
• On the maximum number of maximum independent sets in connected graphs
• Independent packings in structured graphs
• Trees with the second largest number of maximal independent sets
• Maximal independent sets in bipartite graphs
• Maximal and maximum independent sets in graphs with at mostr cycles
• Title not available (Why is that?)
• The number of maximum independent sets in graphs
• The complexity of dissociation set problems in graphs
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• Maximal independent sets in caterpillar graphs
• An improved algorithm for the vertex cover \(P_3\) problem on graphs of bounded treewidth
• On graphs with the third largest number of maximal independent sets
• Maximizing the number of independent sets of fixed size in connected graphs with given independence number
• Trees with the second and third largest number of maximal independent sets
• On the maximum number of minimum dominating sets in forests
• The maximum number of maximum dissociation sets in trees

Cited In (11)

• The maximum number of maximum dissociation sets in trees
• Maximum dissociation sets in subcubic trees
• Enumerating maximal dissociation sets in three classes of grid graphs
• A bound on the dissociation number
• Maximal and maximum dissociation sets in general and triangle-free graphs
• 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
• On the \(A_\alpha\)-index of graphs with given order and dissociation number
• Uniformly dissociated graphs

This page was built for publication: On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6178795)